Home > By category > Scripts >Communication > Multiple-root polynomial solved by partial fraction expansion



Multiple-root polynomial solved by partial fraction expansion

  • Downloads: 
  • Views: 
  • Rating:

A given polynomial p(x) is transformed into a rational function r(x). The poles and residues of the derived rational function are found to be equivalent to the roots and multiplicities of the original polynomial.
p(x) = Given polynomial
= PROD[k=1:K]{(x - z_k)^m_k}
d(x) = (d/dx)p(x)
g(x) = GCD(p(x),d(x))
u(x) = p(x)/g(x)
w(x) = (d/dx)u(x)
v(x) = d(x)/g(x)
r(x) = v(x)/u(x)
= SUM[k=1:K]{m_k/(x - z_k)}
Thus, the roots z_k are computed from solving the simple-root polynomial u(x)=0, instead of the original multiple-root polynomial p(x)=0; and the multiplicities m_k are determined as the partial fraction expansion coefficients of the derived rational function r(x)=v(x)/u(x),
z_k = Roots(u(x)), k=1,K
m_k = v(z_k)/w(z_k), k=1,K
In addition, re-constructing a polynomial pz(x) from the computed z_k and m_k, the overall deviation error of the original polynomial p(x) is calculated,
er = Norm(pz - p)/Norm(p)
The polynomial GCD is calculated from "Monic polynomial subtraction" derived from the longhand polynomial division in classical Euclidean GCD algorithm. It requirs only simple algebric operations without any high mathematics.
The source code contains total of only 43 lines, using merely basic built-in MATLAB functions, and applying only existing double precision. Amazingly, it gives the expected results of test polynomials of very high degree , such as
p(x) = (x - 123456789)^30
p(x) = (x + 100)^20 * (100x-1)^10
p(x) = (x+1)^40 * (x-2)^30 * (x+3)^20 * (x-4)^10
p(x) = (x + 1)^1000

______________________________________________________

The code is list here for reader's convenince. (only 43 lines)

function [zm,er] = polyroots(p)
% *** A polymonial with multiple roots ***
% Solved via partial fraction expansion
d = polyder(p);
g = polygcd(p,d);
u = deconv(p,g);
v = deconv(d,g);
w = polyder(u);
z = roots(u);
m = round(abs(polyval(v,z)./polyval(w,z)));
zm = [z,m]; % p,d,g,u,v,w,z,m,zm
pz = polyget([m,-z,ones(length(z),1)])*p(1);
er = norm(pz-p)/norm(p); % pz,er
function g = polygcd(p,q)
% *** GCD of a pair of polynomials ***
% by "Monic polynomial subtraction"
n = length(p)-1; nc = max(find(p))-1;
m = length(q)-1; mc = max(find(q))-1;
nz = min(n-nc,m-mc);
if nc*mc == 0, g = [1,zeros(1,nz)]; return, end;
p2 = [p(1:nc+1)];
p3 = [q(1:mc+1)];
for k = 1:nc+nc,
p3 = [p3(min(find(abs(p3)>1.e-6)): max(find(abs(p3)>1.e-6)))];
p1 = [p2/p2(1)]; % k,p1,
p2 = [p3/p3(1)];
p3 = [p2,zeros(1,length(p1)-length(p2))]-[p1,zeros(1,length(p2)-length(p1))];
if norm(p3)/norm(p2) < 1.e-3, break; end;
end;
g = [p1,zeros(1,nz)];
function p = polyget(A)
% *** A polynomial coefficient vector from sub-polynomial factors ***
p = 1;
for i = 1:length(A(:,1)),
q = 1;
for j = 1:A(i,1),
q = conv(q,A(i,max(find(A(i,:))):-1:2));
end;
p = conv(p,q);
end;

_____________________________________________________

Typical Numerical Example:

>> % Contruct a test polynomial:
>> p = poly([ 1 1 1 1 1 1 1 -1 -1 -1 -1+2i -1+2i -1+2i -1-2i -1-2i -1-2i 2 2 3 3 +i +i +i -i -i -i -3 0 0 0 0 0 ])
p =
1 -5 2 -6 76 140 -802 954 -4251 13663 -18740 28472 -53504 45776 5212 -77580 185243 -220631 104794 52458 -193356 248612 -146266 9202 65791 -87555 55800 -13500 0 0 0 0 0
>> % Roots and multiplicities for the polynomial are computed.
>> zm = polyroots(p)
zm =
3.0000 -------------- : 2.0000
-3.0000 -------------- : 1.0000
-1.0000 + 2.0000i ---: 3.0000
-1.0000 - 2.0000i ---: 3.0000
2.0000 ---------------: 2.0000
-1.0000 ---------------: 3.0000
-0.0000 + 1.0000i ---: 3.0000
-0.0000 - 1.0000i ---: 3.0000
1.0000 ---------------: 7.0000
0.0000 ---------------: 5.0000

Free download from Shareware Connection - A given polynomial p(x) is transformed into a rational function r(x).

Publisher: Feng Cheng Chang | License: Freeware | Price: 0.00
Version: 1.0 | Size: 10 KB | Platform: Matlab, Scripts
Released Date: 22-03-2013 | Rating: 0 | Title: Multiple-root polynomial solved by partial fraction expansion

Author Url: http://www.mathworks.com
Program Info Url: http://www.mathworks.com
Download Url: http://www.mathworks.com/matlabcentral/fx_files/22375/12/polyroots.zip

More downloads from Multiple-root polynomial solved by partial fraction expansion publisher Feng Cheng Chang:

Polynomial coefficient vector derived from sub-polynomial factors - This routine is mainly to be used for creating test polynomials to

Polynomial division by convolution -- up to finite terms - Polynomial division by convolution.

Solving multiple-root polynomials - The MATLAB script file M_polyroots.m is to compute all the roots with multiplicities of any given polynomials

Multiple-root polynomial solved by partial fraction expansion keywords:
Multiple-root polynomial solved by partial fraction expansion related downloads:

Polynomial coefficient vector derived from sub-polynomial factors - This routine is mainly to be used for creating test polynomials to

Free Fraction Calculator - Free Fraction Calculator is a handy application that can help students to perform multiple faction calculations.

Apply Word Wrap To Multiple Text Files Software - Wrap text (insert a carriage return) by number of words, by number of characters

Break Reminder - Break Reminder is designed to prevent and assist convalscence of OOS/RSI. Runs in the background monitoring computer use, giving appropriate pause and/or break reminders. Highly user configurable. Logs events. Many users around the World love it.

Multiple Coherence Function - For a system having multiple inputs x and outputs y, the partial coherence is the coherence computed between any individual input and the output when the effect of all other inputs is removed from the output by a linear least squares prediction

Shareware Connection periodically updates pricing and software information of 'Multiple-root polynomial solved by partial fraction expansion' from company source 'Feng Cheng Chang' , so some information may be slightly out-of-date. You should confirm all information before relying on it. Software piracy is theft,  Using 'Multiple-root polynomial solved by partial fraction expansion' crack, password, serial numbers, registration codes, key generators is illegal and prevent future development of Multiple-root polynomial solved by partial fraction expansion.

New Reviews

SnapCrab - Nearly every PC users need to take screenshots from time to time, whether it is for personal or professional needs. While using the basic Windows screenshot capture method is available, it is not adequate for everyone. When you want to capture ...

RawTherapee - There are so many image editors out there but when it comes to powerful and versatile RAW file editors, the choices are somewhat limited. With Adobe switching to Cloud-based subscriptions for most of its apps, semiprofessional users including ...

Potatoshare Systemnanny - People use PCs for various needs nowadays. A computer is not used to run office productivity or accounting software alone anymore. It is also used for tasks like web browsing, media playback, file conversion, and myriad related needs. After ...

Bvckup - There is no denying the reality that computers have become a part and parcel of human existence. From education, work, entertainment and data storage, computers are required at every step of life. Safety of data is of paramount importance to PC ...

Efham internet booster - Without using the web, you cannot accomplish a lot of things in life easily. However, the speed of internet access does play a role behind your web usage experience. At times, you may have to cope with sluggish web page rendering, buffering while ...

CherryPlayer - When you want to watch movies, online videos or listen to music tracks, using a suitable application is required. There is no hard and fast rule that you have to stick to Windows default media player software for such needs. There are plenty of ...

Internet Explorer 10 - Up to the late 1990s, the web browser used by the bulk of Windows users was invariably Internet Explorer while Netscape played the second fiddle. The scene was relatively identical post 2000 but emergence of Firefox and later Google Chrome ...

dMaintenance - As a computer user, you may need to deal with several types of applications. For a lot of Windows users, the integrated tools of the OS may not suffice at times. They may need to use several third party apps for needs such as entertainment, ...

Nero Kwik Media - Nero is known mostly for its legendary disc burning software that has metamorphosed into a media editing powerhouse over a decade. The multimedia suite offered by the company caters to needs of intermediate and advanced users well but its price ...

Emsisoft Emergency Kit - The way malware creators and hackers are adapting to newer measures to sneak past PC security, it is no longer enough to stay complacent after installing a standalone antivirus. You never know when a stealthy malware sneaks past its scan and ...




New Downloads

SoundTaste Audio Converter

This program is a
professional, fast and
easy-to-use audio conversion
utility to help you convert
many audio files in ...

Easy Audio Extractor

It is the Pro version of Free
Audio Extractor. It provides
wizard mode &
user-friendly operating window
to guide the ...

Availability Booking
Calendar

Availability Booking Calendar
is a multi-calendar booking
system that enables your site
users to reserve dates/nights
...

Modis Tile pixel

MODLAND Tile Calculator

WebLogger

WebLogger is a php-based
application designed to help
Amateur Radio operators log
radio traffic.

matlab2tikz

As of now, matlab2tikz does
not support the conversion of
all possible MATLAB figures.

ActiveX control of APT
Thorlabs positioning stages

This code shows how to control
the APT Thorlabs positioning
system using the third party
ActiveX controls

ffndgrid Fast 'n' Furious
N-D data gridding

FFNDGRID grids unevenly spaced
data.

ExtPhaseCorrelation

I tried to make the
implementation of the paper
entitled "Extension of Phase
Correlation to Subpixel
Registration"

Coordinate descent for
Compressed Sensing

This package has solvers for
constrained and unconstrained
L1 minimization, which is
useful for compressed sensing

WP Tweet Search Tooltip

Adds a tooltip on an chosen
keyword for a search via
twitter.

Mollio CSS/HTML Templates

Mollio is a simple set of
html/css templates.