Multipleroot polynomial solved by partial fraction expansion 1.0 
Date Added: September 07, 2013  Visits: 267 


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 simpleroot polynomial u(x)=0, instead of the original multipleroot 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, reconstructing 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 builtin 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 * (100x1)^10 p(x) = (x+1)^40 * (x2)^30 * (x+3)^20 * (x4)^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(pzp)/norm(p); % pz,erfunction 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(nnc,mmc); 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.e6)): max(find(abs(p3)>1.e6)))]; 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.e3, break; end; end; g = [p1,zeros(1,nz)];function p = polyget(A) % *** A polynomial coefficient vector from subpolynomial 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 12i 12i 12i 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

License: Freeware  Size: 10 KB 
Screen Savers

Prison Break Season 3 Screensaver 1
Season 3 of Prison Break is scheduled to premiere on September 17, 2007; the first seventeen minutes of the season premiere were released on the official website on August 24, 2007. Series creator Paul Scheuring has commented that the third season... 
2.15 MB  
Networking

Manual Frame Break Script 1.1
This script allows your visitors to break out of frames with a simple link. It helps you to easily choose whether or not to view the page within frames. 
10 KB  
Networking

javascript Break Out of Frames Script 1.1
If your page is captured inside of a frame on another site, this script will break your page out of the frameset and make your page the parent (that is, top) page. 
10 KB  
Time & Clock Tools

RSIShield 4.1
Very powerful break software. This program helps you fight RSI (repetitive strain injury). RSIShield offers the following things: 3 kinds of breaks (micro, medium and rest), Intelligent break system, Break enforcement, Extensive statistics,... 
14 KB  
Application AddIns

LanDTM 6.0.0.0
There is not any professional program on internet like this and you can get it without any effort. I think this could be a handicap because it's dificult to believe, but it's true; try it and you'll be surprised. It's not only a program to... 
12.28 MB  
Text Chat Clients

prophorBNCd 0.2.2
prophorBNCd is an easy multiuser BNC server for IRC. It is used to keep the IRC connection open continuously. Whats New in This Release: AWAYNICK:  /quote SET_AWAYNICK nickname  set a awaynick  /quote NULL_AWAYNICK  reset the awaynick... 
45.06 KB  
Puzzles

Genuts Breaker 1.6
Genuts Breaker project is a remake of the popular classic BreakOut game. How to play "Genuts Breaker":. Genuts provides a consistent Java framework for game development, and gamerelated services. It contains a library primarily intended for... 
76.8 KB  
Time & Clock Tools

PC WorkBreak 1.02
PC WorkBreak provides proper reminders to reduce your RSI (Repetitive Strain Injury) risk. It offers multitype break reminders such as microbreak, stretch, eye exercises and walk, based on your PC usage model. Compliance rates are also provided.... 
2.16 MB  
Finance

DocumentBurster 5.2.8
DocumentBurster is a solution to merge, break up and distribute relevant reports to your clients by either email, FTP, FTPS, SFTP, TFTP, Windows shared drives, Unix Samba servers, WebDAV or enterprise portals such as Microsoft SharePoint. The... 
29.54 MB  
Home & Leisure

myWork Coach (formerly Take 5) 1.6.4.3
myWork Coach is a small and handy application that will notify you when you should take a break from work. Just select your working period and after your computer breaks. Notifications and / or automatic locking / standby mode or logoff. for... 
Scripts

Free Ecommerce website creator 1.2
Free Ecommerce website creator is a free PHP shop creating script. This allows you to put a online shop on your own website. Create your own free ecommerce website for Your Business. Create an online shop using easyGUI online shop creator. The... 
1.44 KB  
Scripts

MochiGames PHP Script ZDR 1.00
MochiGames PHP Script ZDR is web site, ready for use, for flash games. These flash games are downloaded automatically by "MochiGames PHP Script ZDR" from MochiGames media. The use of the games is free, you can use your own Mochi Publisher ID and... 
368.54 KB  
Scripts

Php Chat 2.0
Add a free php site, single signon and multiple skins, 100% free 1. Server Modes: The chat server has paid mode and free mode. If the free chat mode, a free chat room will be assigned to your website with your domain as the room name. 2.... 
938.87 KB  
Scripts

Nibbleblog 3.0.1
Nibbleblog it's a powerful engine for creation and manipulation of BLOG's completely free. Very simple to install and configure (Only 1 step). The database used is based on XML files and this way it is not necessary to use MySQL or similar DBMS.... 
371.09 KB  
Scripts

PHP File Manager  CloudOsys 2.9b8
CloudOsys is a PHP file manager, a tool that allows your visitors upload files such as media content directly to your website. Your visitors will upload files directly to your website, where they can share and comment on them. Through cloud... 
1.41 MB  
Communication

Contact Form Script 1
This PHP script is a fully functioning contact form which can be easily installed on your own website. It enables users to contact you directly by filling out the form. The PHP script is completely FREE to use, and none of the code is encoded... 
19 KB  
Communication

Ethernet Source with SimEvents 1.1
When audio or video is transmitted over an Ethernet network, the data is usually transmitted in bursts of packets with long idle times in between bursts. SimEvents is a good tool for modeling those types of sources and studying the effects of... 
2.8 MB  
Communication

Autocorrelation and Crosscorrelation function of gold sequence 1.0
This mfile finds and plots the autocorrelation and crosscorrelation function(ACF and CCF) of generated Gold codes of length 31.Crosscorrelations are three valued. 
10 KB  
Communication

Zoom Spectrum 1.0
This function returns N point DFT samples of 2dw band of Fourier transform of a sequence. Typically, fft() returns N samples of Fourier transform ranging from 0 to 2pi. This function takes the Npoint DFT samples and returns Npoint samples... 
10 KB  
Communication

BER of BPSK DSSS System 1.0
This mfile finds the bit error rate performance of BPSK DSSS system over (i) AWGN channel and (ii) Slow Rayleigh fading channel corrupted by AWGN. Compare the performance with simple BPSK system.In this simulation I have used two functions.So to... 
10 KB 