{"id":451,"date":"2013-01-21T12:27:45","date_gmt":"2013-01-21T17:27:45","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=451"},"modified":"2013-05-02T10:00:10","modified_gmt":"2013-05-02T15:00:10","slug":"reduced-penultimate-remainder","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2013\/01\/21\/reduced-penultimate-remainder\/","title":{"rendered":"Reduced Penultimate Remainder"},"content":{"rendered":"<!DOCTYPE html\r\n  PUBLIC \"-\/\/W3C\/\/DTD HTML 4.01 Transitional\/\/EN\">\r\n<style type=\"text\/css\">\r\n\r\nh1 { font-size:18pt; }\r\nh2.titlebg { font-size:13pt; }\r\nh3 { color:#4A4F55; padding:0px; margin:5px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:11pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }\r\nh4 { color:#4A4F55; padding:0px; margin:0px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:10pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }\r\n   \r\np { padding:0px; margin:0px 0px 20px; }\r\nimg { padding:0px; margin:0px 0px 20px; border:none; }\r\np img, pre img, tt img, li img { margin-bottom:0px; } \r\n\r\nul { padding:0px; margin:0px 0px 20px 23px; list-style:square; }\r\nul li { padding:0px; margin:0px 0px 7px 0px; background:none; }\r\nul li ul { padding:5px 0px 0px; margin:0px 0px 7px 23px; }\r\nul li ol li { list-style:decimal; }\r\nol { padding:0px; margin:0px 0px 20px 0px; list-style:decimal; }\r\nol li { padding:0px; margin:0px 0px 7px 23px; list-style-type:decimal; }\r\nol li ol { padding:5px 0px 0px; margin:0px 0px 7px 0px; }\r\nol li ol li { list-style-type:lower-alpha; }\r\nol li ul { padding-top:7px; }\r\nol li ul li { list-style:square; }\r\n\r\npre, tt, code { font-size:12px; }\r\npre { margin:0px 0px 20px; }\r\npre.error { color:red; }\r\npre.codeinput { padding:10px; border:1px solid #d3d3d3; background:#f7f7f7; }\r\npre.codeoutput { padding:10px 11px; margin:0px 0px 20px; color:#4c4c4c; }\r\n\r\n@media print { pre.codeinput, pre.codeoutput { word-wrap:break-word; width:100%; } }\r\n\r\nspan.keyword { color:#0000FF }\r\nspan.comment { color:#228B22 }\r\nspan.string { color:#A020F0 }\r\nspan.untermstring { color:#B20000 }\r\nspan.syscmd { color:#B28C00 }\r\n\r\n.footer { width:auto; padding:10px 0px; margin:25px 0px 0px; border-top:1px dotted #878787; font-size:0.8em; line-height:140%; font-style:italic; color:#878787; text-align:left; float:none; }\r\n.footer p { margin:0px; }\r\n\r\n  <\/style><div class=\"content\"><!--introduction--><p>I investigated the reduced penultimate remainder algorithm in an undergraduate research project under professor John Todd at Caltech in 1961. I remember it today for two reasons.  First, I learned what penultimate means. And second, it is the most obscure, impractical algorithm that I know. I suspect none of my readers have ever heard of it.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#a89997bf-afe7-448e-b319-949fee716fa3\">Penultimate<\/a><\/li><li><a href=\"#dc96e981-0be4-43a2-ab69-5950bf5fce40\">Reduced Penultimate Remainder<\/a><\/li><li><a href=\"#b3163724-b13e-448a-90c4-dfae660b5671\">An Example<\/a><\/li><li><a href=\"#531e4f1a-8de2-43c8-a577-5bc7153b52ec\">Reduced Penultimate Remainder Algorithm<\/a><\/li><li><a href=\"#8b8c4381-310f-4427-8e5c-ea56adf425f7\">A. C. Aitken<\/a><\/li><li><a href=\"#19e9a825-cd34-4e23-9e2f-0078be8ba71c\">Householder's Comments<\/a><\/li><li><a href=\"#63bb4a56-ce66-4f3a-8a57-c8f12f91a12f\">MATLAB Code<\/a><\/li><li><a href=\"#81933d2e-2100-4d5f-9894-838d91d405b5\">Example, continued<\/a><\/li><li><a href=\"#8fd66a0e-8bd0-43f8-ba3b-b633a9954deb\">Another Example<\/a><\/li><li><a href=\"#3d0fce4b-02c7-4230-b6f9-a1f6c7ca793e\">Conclusions<\/a><\/li><li><a href=\"#3818a76e-8b1e-4cf4-8090-4ba218647757\">References<\/a><\/li><\/ul><\/div><h4>Penultimate<a name=\"a89997bf-afe7-448e-b319-949fee716fa3\"><\/a><\/h4><p><i>Penultimate<\/i> means \"next to last\".  November is the <i>penultimate<\/i> month of the year.  In the fifty-plus years since I learned its meaning, I've never had a chance to use penultimate in everyday conversation, or in my writing.  I think of it as British English.  Is it?<\/p><h4>Reduced Penultimate Remainder<a name=\"dc96e981-0be4-43a2-ab69-5950bf5fce40\"><\/a><\/h4><p>Start with two polynomials, both with leading coefficient equal to one. When you divide one polynomial into the other using long division, you usually stop when the degree of the remainder is one less than the degree of the divisor.  But instead, stop one step earlier, with the <i>penultimate<\/i> remainder.  Then scale the leading coefficient of the remainder to be equal to one. This is the <i>reduced penultimate remainder<\/i>.  If the original divisor had actually been an exact factor of the dividend, then this reduced remainder would be equal to the divisor.  Iterating the process with exact divisors exhibits fixed points.<\/p><h4>An Example<a name=\"b3163724-b13e-448a-90c4-dfae660b5671\"><\/a><\/h4><p>Our example involves dividing $q(x) = x^2 - 10x + 5$ into $p(x) = x^5 - 15x^4 + 85x^3 - 225x^2 + 274x - 120$. Here is a scan of one step of the long division carried out by hand. (I don't know enough LaTeX to be able to do the typesetting.)<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/scan.jpg\" alt=\"\"> <\/p><p>The reduced penultimate remainder is $r(x) = x^2 + 1.24x - 1.20$. Since $r(x)$ is not close to $q(x)$, we can conclude that $q(x)$ is not close to a factor of $p(x)$ and consequently that the roots of $q(x)$ are not close to the roots of $p(x)$.  I will return to this example later.<\/p><h4>Reduced Penultimate Remainder Algorithm<a name=\"531e4f1a-8de2-43c8-a577-5bc7153b52ec\"><\/a><\/h4><p>If the divisor happens to be a factor of the dividend, then the reduced penultimate remainder process is a fixed point iteration. In 1943, Shi-nge Lin suggested that starting with an initial approximation that is nearly a factor and repeating the RPR process, the iteration might converge to a factor and hence could be used to find roots of polynomials. I do not know who Shi-nge Lin was and have not actually seen his original paper.<\/p><h4>A. C. Aitken<a name=\"8b8c4381-310f-4427-8e5c-ea56adf425f7\"><\/a><\/h4><p>A. C. Aitken(1895-1967) wrote papers about Lin's idea in 1952 and 1955. Aitken was born in New Zealand, educated in Scotland, and became a professor of mathematics at the University of Edinburgh.  He made many contributions to many areas of mathematics.  In numerical analysis he is best known for the delta-squared sequence acceleration technique. His prodigious memory made some aspects of his life unpleasant. He served with the New Zealand forces in World War I and his memories of the battle at Gallipoli haunted him throughout his life.<\/p><p>John Todd was the professor at Caltech who introduced me to numerical analysis, matrices, and computing.  I believe that Todd knew Aitken personally and he was certainly familiar with his work. So he suggested I investigate the method and I read Aitken's papers. I wrote programs in machine language for the Burroughs 205 Datatron. Unfortunately, about all I can remember about the project is the name of the algorithm.<\/p><h4>Householder's Comments<a name=\"19e9a825-cd34-4e23-9e2f-0078be8ba71c\"><\/a><\/h4><p>Alston Householder(1904-1993) is one of my heroes.  I knew him quite well. He's the fourth guy from the left in our photo of the organizing committee of the 1964 Gatlinburg Conference on Numerical Algebra<\/p><pre class=\"codeinput\">load <span class=\"string\">gatlin<\/span>\r\nimage(X)\r\ncolormap(map)\r\naxis <span class=\"string\">off<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/rpr_blog_01.png\" alt=\"\"> <p>I just learned that Householder wrote a paper about the Reduced Penultimate Remainder algorithm in 1970, ten years after I did my undergraduate research project.  I didn't know about that paper until I came across it while writing this blog.<\/p><p>Householder makes some very candid comments about the earlier papers by Lin and Aitken.  He says \"Lin's development is complicated and unsuggestive\". He says \"Aitken's derivation of the conditions for convergence is very sketchy and leaves much to the reader.\" Householder's paper was published in the SIAM Journal of Applied Math in 1970. I don't think we could make comments like these in SIAM papers today.<\/p><p>Aitken had introduced a device called the catalytic multiplier and Householder tries to explain it.  I do not understand his paper at all. Near the end of the paper he says \"In notation elsewhere used by the author ...\"  That is not very helpful.  I'm afraid that is this particular paper Alston is no clearer than the authors he is criticizing. I can say this in a blog.<\/p><h4>MATLAB Code<a name=\"63bb4a56-ce66-4f3a-8a57-c8f12f91a12f\"><\/a><\/h4><pre class=\"codeinput\">type <span class=\"string\">rpr<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction q = rpr(p,q)\r\n% RPR Reduced Penultimate Remainder.\r\n% r = rpr(p,q), for polynomials p and q.\r\n% Assume p(1) = 1, q(1) = 1.\r\nfor c = 1:15\r\n   % Polynomial long division.\r\n   % Stop when degree of r = degree of q.\r\n   n = length(p);\r\n   m = length(q);\r\n   r = p(1:m);\r\n   for k = m+1:n\r\n      r = r - r(1)*q;\r\n      r = [r(2:end) p(k)];\r\n   end\r\n   q = r\/r(1);\r\n   disp(q)\r\nend\r\n\r\n<\/pre><h4>Example, continued<a name=\"81933d2e-2100-4d5f-9894-838d91d405b5\"><\/a><\/h4><p>The example I used in hand calculation above is the polynomial whose roots are the integers from one to five.<\/p><pre class=\"codeinput\">p = charpoly(diag(1:5))\r\n<\/pre><pre class=\"codeoutput\">p =\r\n     1   -15    85  -225   274  -120\r\n<\/pre><p>The starting guess is a deliberately bad approximation to a quadratic factor.<\/p><pre class=\"codeinput\">q = [1 -10 5]\r\n<\/pre><pre class=\"codeoutput\">q =\r\n     1   -10     5\r\n<\/pre><p>Let's run 15 iterations<\/p><pre class=\"codeinput\">format <span class=\"string\">long<\/span>\r\nformat <span class=\"string\">compact<\/span>\r\nrpr(p,q)\r\n<\/pre><pre class=\"codeoutput\">   1.000000000000000   1.240000000000000  -1.200000000000000\r\n   1.000000000000000  -1.067114979620489   0.318854992571954\r\n   1.000000000000000  -1.723550954295960   0.821587108699062\r\n   1.000000000000000  -2.062229096576079   1.106543069892922\r\n   1.000000000000000  -2.272884387512085   1.294527998591067\r\n   1.000000000000000  -2.417143826065064   1.428233837285976\r\n   1.000000000000000  -2.522010435111559   1.527880806063684\r\n   1.000000000000000  -2.601434375494343   1.604615444108659\r\n   1.000000000000000  -2.663426234246922   1.665180563853953\r\n   1.000000000000000  -2.712940049546721   1.713920778923779\r\n   1.000000000000000  -2.753213571017107   1.753767759646395\r\n   1.000000000000000  -2.786455813893868   1.786771702201661\r\n   1.000000000000000  -2.814227004785662   1.814408345663866\r\n   1.000000000000000  -2.837661124583663   1.837765841878627\r\n   1.000000000000000  -2.857602508367706   1.857663278238952\r\nans =\r\n   1.000000000000000  -2.857602508367706   1.857663278238952\r\n<\/pre><p>It's converging, slowly, to the factor $x^2 - 3x + 2$ with roots $1$ and $2$. It takes about 300 iterations to reach this factor to double precision accuracy.<\/p><h4>Another Example<a name=\"8fd66a0e-8bd0-43f8-ba3b-b633a9954deb\"><\/a><\/h4><p>One of my favorite polynomials is $p(x) = x^3 - 2x - 5$.  It's only real root is near $2.09$.  Let's try to find it.<\/p><pre class=\"codeinput\">p = [1 0 -2 -5]\r\nq = [1 -2]\r\nrpr(p,q)\r\n<\/pre><pre class=\"codeoutput\">p =\r\n     1     0    -2    -5\r\nq =\r\n     1    -2\r\n   1.000000000000000  -2.500000000000000\r\n   1.000000000000000  -1.176470588235294\r\n   1.000000000000000   8.117977528089890\r\n   1.000000000000000  -0.078245352175702\r\n   1.000000000000000   2.507676417722349\r\n   1.000000000000000  -1.165924862052266\r\n   1.000000000000000   7.804948516596162\r\n   1.000000000000000  -0.084864830447043\r\n   1.000000000000000   2.509035084827172\r\n   1.000000000000000  -1.164074683720088\r\n   1.000000000000000   7.752777799980693\r\n   1.000000000000000  -0.086050279678108\r\n   1.000000000000000   2.509290208665588\r\n   1.000000000000000  -1.163727809437372\r\n   1.000000000000000   7.743083431952472\r\nans =\r\n   1.000000000000000   7.743083431952472\r\n<\/pre><p>No luck, it's not going to converge. The real root repels any attempt to find it with this iteration.<\/p><h4>Conclusions<a name=\"3d0fce4b-02c7-4230-b6f9-a1f6c7ca793e\"><\/a><\/h4><p>Finding polynomial roots is not a very important task and this algorithm is not very good at it anyway. Its convergence properties are too unreliable. So for me, this is just a quirky memory. If anybody else has heard of the reduced penultimate remainder algorithm, please contribute a comment.<\/p><h4>References<a name=\"3818a76e-8b1e-4cf4-8090-4ba218647757\"><\/a><\/h4><p>[1] A. C. AITKEN, Studies in practical mathematics. VII. On the theory of factorizing polynomials by iterated division, Proc. Roy. Soc. Edinburgh Sec..A, 63 (1952), pp. 326-335.<\/p><p>[2] A. C. AITKEN, Note on the acceleration of Lin's process of iterated penultimate remainder, Quart. J. Mech.  Appl. Math., 8 (1955), pp. 251-258.<\/p><p>[3] SHI-NGE LIN, A method for finding roots of algebraic equations, J. Math. Phys. Mass. Inst. Tech., 22 (1943), pp. 60-77.<\/p><p>[4] ALSTON S. HOUSEHOLDER, On the penultimate remainder algorithm and the catalytic multiplier, SIAM J. Appl. Math., 19 (1970), pp. 668-671.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_2e3195996e8f4ae29283a2e5827d0b10() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='2e3195996e8f4ae29283a2e5827d0b10 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 2e3195996e8f4ae29283a2e5827d0b10';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2012 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_2e3195996e8f4ae29283a2e5827d0b10()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2012b<br><\/p><p class=\"footer\"><br>\r\n      Published with MATLAB&reg; R2012b<br><\/p><\/div><!--\r\n2e3195996e8f4ae29283a2e5827d0b10 ##### SOURCE BEGIN #####\r\n%% Reduced Penultimate Remainder\r\n% I investigated the reduced penultimate remainder algorithm in an\r\n% undergraduate research project under professor John Todd at Caltech in 1961.\r\n% I remember it today for two reasons.  First, I learned what penultimate means.\r\n% And second, it is the most obscure, impractical algorithm that I know.\r\n% I suspect none of my readers have ever heard of it.\r\n\r\n%% Penultimate\r\n% _Penultimate_ means \"next to last\".  November is the _penultimate_ \r\n% month of the year.  In the fifty-plus years since I learned its meaning,\r\n% I've never had a chance to use penultimate in everyday conversation, or\r\n% in my writing.  I think of it as British English.  Is it?\r\n\r\n%% Reduced Penultimate Remainder\r\n% Start with two polynomials, both with leading coefficient equal to one.\r\n% When you divide one polynomial into the other using long division,\r\n% you usually stop when the degree of the remainder is one\r\n% less than the degree of the divisor.  But instead, stop one step earlier,\r\n% with the _penultimate_ remainder.  Then scale the leading\r\n% coefficient of the remainder to be equal to one.\r\n% This is the _reduced penultimate remainder_.  If the original divisor had\r\n% actually been an exact factor of the dividend, then this reduced remainder\r\n% would be equal to the divisor.  Iterating the process with exact \r\n% divisors exhibits fixed points.\r\n\r\n%% An Example\r\n% Our example involves dividing $q(x) = x^2 - 10x + 5$ into\r\n% $p(x) = x^5 - 15x^4 + 85x^3 - 225x^2 + 274x - 120$.\r\n% Here is a scan of one step of the long division carried out by hand.\r\n% (I don't know enough LaTeX to be able to do the typesetting.)\r\n%\r\n% <<scan.jpg>>\r\n%\r\n%%\r\n% The reduced penultimate remainder is $r(x) = x^2 + 1.24x - 1.20$. \r\n% Since $r(x)$ is not close to $q(x)$, we can conclude that $q(x)$ is not\r\n% close to a factor of $p(x)$ and consequently that the roots of $q(x)$\r\n% are not close to the roots of $p(x)$.  I will return to this example later.\r\n\r\n%% Reduced Penultimate Remainder Algorithm\r\n% If the divisor happens to be a factor of the dividend, then\r\n% the reduced penultimate remainder process is a fixed point iteration.\r\n% In 1943, Shi-nge Lin suggested that starting with an initial approximation\r\n% that is nearly a factor and repeating the RPR process, the iteration might\r\n% converge to a factor and hence could be used to find roots of polynomials.\r\n% I do not know who Shi-nge Lin was and have not actually seen his original\r\n% paper.\r\n\r\n%% A. C. Aitken\r\n% A. C. Aitken(1895-1967) wrote papers about Lin's idea in 1952 and 1955.\r\n% Aitken was born in New Zealand, educated in Scotland, and became a professor\r\n% of mathematics at the University of Edinburgh.  He made many contributions to\r\n% many areas of mathematics.  In numerical analysis he is best known\r\n% for the delta-squared sequence acceleration technique.\r\n% His prodigious memory made some aspects of his life unpleasant.\r\n% He served with the New Zealand forces in World War I and his memories\r\n% of the battle at Gallipoli haunted him throughout his life.\r\n%\r\n% John Todd was the professor at Caltech who introduced me to numerical\r\n% analysis, matrices, and computing.  I believe that Todd knew Aitken\r\n% personally and he was certainly familiar with his work.\r\n% So he suggested I investigate the method and I read Aitken's papers.\r\n% I wrote programs in machine language for the Burroughs 205 Datatron.\r\n% Unfortunately, about all I can remember about the project\r\n% is the name of the algorithm.\r\n\r\n%% Householder's Comments\r\n% Alston Householder(1904-1993) is one of my heroes.  I knew him quite well.\r\n% He's the fourth guy from the left in our photo of the organizing\r\n% committee of the 1964 Gatlinburg Conference on Numerical Algebra\r\n\r\nload gatlin\r\nimage(X)\r\ncolormap(map)\r\naxis off\r\n\r\n%%\r\n% I just learned that Householder wrote a paper about the Reduced Penultimate\r\n% Remainder algorithm in 1970, ten years after I did my undergraduate\r\n% research project.  I didn't know about that paper until I came across it\r\n% while writing this blog.  \r\n%\r\n% Householder makes some very candid comments about the earlier papers by\r\n% Lin and Aitken.  He says \"Lin's development is complicated and unsuggestive\".\r\n% He says \"Aitken's derivation of the conditions for convergence is very\r\n% sketchy and leaves much to the reader.\"\r\n% Householder's paper was published in the SIAM Journal of Applied Math in 1970.\r\n% I don't think we could make comments like these in SIAM papers today.  \r\n%\r\n% Aitken had introduced a device called the catalytic multiplier and\r\n% Householder tries to explain it.  I do not understand his paper at all.\r\n% Near the end of the paper he says \"In notation elsewhere used by the\r\n% author ...\"  That is not very helpful.  I'm afraid that is this particular\r\n% paper Alston is no clearer than the authors he is criticizing.\r\n% I can say this in a blog.\r\n\r\n%% MATLAB Code\r\n\r\ntype rpr\r\n\r\n%% Example, continued\r\n%\r\n% The example I used in hand calculation above is the polynomial whose\r\n% roots are the integers from one to five.\r\n\r\np = charpoly(diag(1:5))\r\n\r\n%%\r\n% The starting guess is a deliberately bad approximation to a quadratic factor.\r\n\r\nq = [1 -10 5]\r\n\r\n%%\r\n% Let's run 15 iterations\r\n\r\nformat long\r\nformat compact\r\nrpr(p,q)\r\n\r\n%% \r\n% It's converging, slowly, to the factor $x^2 - 3x + 2$ with roots $1$ and $2$.\r\n% It takes about 300 iterations to reach this factor to double precision\r\n% accuracy.\r\n\r\n%% Another Example\r\n% One of my favorite polynomials is $p(x) = x^3 - 2x - 5$.  It's only real\r\n% root is near $2.09$.  Let's try to find it.\r\n\r\np = [1 0 -2 -5]\r\nq = [1 -2]\r\nrpr(p,q)\r\n\r\n%%\r\n% No luck, it's not going to converge.\r\n% The real root repels any attempt to find it with this iteration.\r\n\r\n%% Conclusions\r\n% Finding polynomial roots is not a very important task and this algorithm\r\n% is not very good at it anyway.\r\n% Its convergence properties are too unreliable.\r\n% So for me, this is just a quirky memory.\r\n% If anybody else has heard of the reduced penultimate remainder algorithm,\r\n% please contribute a comment.\r\n\r\n%% References\r\n% [1] A. C. AITKEN, Studies in practical mathematics. VII. On the theory of\r\n% factorizing polynomials by iterated division,\r\n% Proc. Roy. Soc. Edinburgh Sec..A, 63 (1952), pp. 326-335.\r\n%%\r\n% [2] A. C. AITKEN, Note on the acceleration of Lin's process of iterated\r\n% penultimate remainder,\r\n% Quart. J. Mech.  Appl. Math., 8 (1955), pp. 251-258.\r\n%%\r\n% [3] SHI-NGE LIN, A method for finding roots of algebraic equations,\r\n% J. Math. Phys. Mass. Inst. Tech., 22 (1943), pp. 60-77.\r\n%%\r\n% [4] ALSTON S. HOUSEHOLDER, On the penultimate remainder algorithm and the\r\n% catalytic multiplier,\r\n% SIAM J. Appl. Math., 19 (1970), pp. 668-671.\r\n\r\n##### SOURCE END ##### 2e3195996e8f4ae29283a2e5827d0b10\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/scan.jpg\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>I investigated the reduced penultimate remainder algorithm in an undergraduate research project under professor John Todd at Caltech in 1961. I remember it today for two reasons.  First, I learned what penultimate means. And second, it is the most obscure, impractical algorithm that I know. I suspect none of my readers have ever heard of it.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2013\/01\/21\/reduced-penultimate-remainder\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[7],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/451"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=451"}],"version-history":[{"count":7,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/451\/revisions"}],"predecessor-version":[{"id":470,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/451\/revisions\/470"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=451"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=451"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}