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).
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
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
123WebMessenger
Voice Audio Processing
Fractal dimension
Yahoo Messenger
PlaySMS
PID Tuning Using Genetic Algorithm
Continuous Sound and Vibration Analysis
Shock Response Spectrum
Grey prediction algorithm for mobile user localization
GSM Traffic Channel Simulator
OFDM LSE Channel Estimation
Wiener filter for Noise Reduction and speech enhancement
Solutions for Digital and Analog Communication Systems, 7Ed by Leon Couch
Using S-Parameters in MATLAB & Simulink
Affiliate Programs
Animation
Auctions
Audio Systems
Banner Rotation
Blog
Bulletin Boards & Forums
Business & Enterprise
Buttons
Calendars & Events
Charts & Graphs
Chat
Classified Ad Managers
Communication
Rational Polynomial Curve Fitting
Polynomial Equations
Polynomial Regressio
Polynomial Worksheets
Jones Polynomial
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.
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 ...


