{"id":440,"date":"2025-03-31T00:22:46","date_gmt":"2025-03-30T16:22:46","guid":{"rendered":"https:\/\/www.toothlessos.xyz\/?p=440"},"modified":"2025-03-31T00:22:57","modified_gmt":"2025-03-30T16:22:57","slug":"the-optimization-set-non-linear-solvers","status":"publish","type":"post","link":"https:\/\/www.toothlessos.xyz\/index.php\/2025\/03\/31\/the-optimization-set-non-linear-solvers\/","title":{"rendered":"The optimization set: Non-linear solvers"},"content":{"rendered":"\n<p>This log will focus on open methods for solving non-linear equations, including <strong>fixed-point iteration<\/strong>, <strong>Newton-Raphson method<\/strong>, <strong>Bairstow&#8217;s method<\/strong>, <strong>Quotient Difference algorithm<\/strong> and <strong>Muller&#8217;s method<\/strong>.<\/p>\n\n\n<p><\/p>\n\n<div class=\"wp-block-aioseo-table-of-contents\"><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-open-close\">Open? Close?<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-general-functions\">General functions<\/a><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-fixed-point-iteration\">Simple fixed-point iteration<\/a><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-simple-fixed-point-iteration\">Description<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-algorithm\">Algorithm<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-convergence\">Convergence<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-aitken-acceleration\">Aitken acceleration<\/a><\/li><\/ul><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-newton-raphson-method\">Newton-Raphson method<\/a><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-update-rule\">Update rule<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-taylor-series\">Taylor series<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-pitfalls\">Pitfalls<\/a><\/li><\/ul><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-secant-method\">Secant method<\/a><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-update-rule\">Update rule<\/a><\/li><\/ul><\/li><\/ul><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-polynomials\">Polynomials<\/a><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-bairstows-method\">Bairstow&#039;s method (for complex roots)<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-quotient-difference-algorithm\">Quotient-Difference Algorithm<\/a><\/li><\/ul><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-quadratic-interpolation\">Quadratic Interpolation<\/a><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-mullers-method\">Muller&#039;s method<\/a><\/li><\/ul><\/li><\/ul><\/div>\n\n\n<p>Slides reference: Prof. Sun, Peng &#8211; <a href=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/Topic-2-Nonlinear-Equation-Solver-Winter-2025.pdf\" title=\"\">Non-Linear Equation Solvers<\/a><\/p>\n\n\n\n<p>Textbook reference: <a href=\"https:\/\/www.academia.edu\/38084603\/Numerical_Methods_for_Engineers_SEVENTH_EDITION\">Numerical Methods for Engineers SEVENTH EDITION<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"aioseo-open-close\">Open? Close?<\/h2>\n\n\n\n<p>The &#8220;close&#8221; methods are actually called <strong>bracketing methods<\/strong>. For these methods, we start with an <strong>interval<\/strong> that brackets the root. Then, we utilize properties of the target function to narrow down the interval iteratively. Typical examples of bracketing methods include the <strong>bisection method<\/strong> and the <strong>false position method<\/strong>.<\/p>\n\n\n\n<p>Open methods, one the other hand, starts the iteration with a single starting value of x or two starting values that do not \u201cbracket\u201d the root. Because of this, they can sometimes <strong>diverge<\/strong> from the true root. However, when they <strong>converge<\/strong>, they usually do so much more quickly than bracketing methods.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"aioseo-general-functions\">General functions<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-fixed-point-iteration\">Simple fixed-point iteration<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"aioseo-simple-fixed-point-iteration\">Description<\/h4>\n\n\n\n<p>For a function <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-5d69cd58dbb471f5e6a3c673b458a5cf_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#40;&#120;&#41;&#32;&#61;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"67\" style=\"vertical-align: -5px;\"\/>, we rearrange the function in the form of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-5dcebf7fa0b66835998f41c3d100a1af_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#32;&#61;&#32;&#103;&#40;&#120;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"66\" style=\"vertical-align: -5px;\"\/> such that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-f4a542920d9c4d0e1234ca44cc3a59b4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#103;&#40;&#120;&#41;&#32;&#61;&#32;&#102;&#40;&#120;&#41;&#32;&#43;&#32;&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"123\" style=\"vertical-align: -5px;\"\/>.<\/p>\n\n\n\n<p>In the case of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-81ba4e72bcaf447eab92dca9b0f143e2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#40;&#120;&#41;&#32;&#61;&#32;&#120;&#94;&#50;&#32;&#45;&#32;&#120;&#32;&#45;&#32;&#50;&#32;&#40;&#120;&#62;&#48;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"194\" style=\"vertical-align: -5px;\"\/>, there are 3 different ways to rearrange them\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-68f57e7834ba6facd8b90e9f6a7fde49_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#32;&#61;&#32;&#120;&#94;&#50;&#32;&#45;&#32;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"81\" style=\"vertical-align: 0px;\"\/><\/li>\n\n\n\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-3f62194d3ec27e27cec1e59cd5fc3d0a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#32;&#61;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#120;&#32;&#43;&#32;&#50;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"90\" style=\"vertical-align: -3px;\"\/><\/li>\n\n\n\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-bc938160750808aa43c91e7853200ca8_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#32;&#61;&#32;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#50;&#125;&#123;&#120;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"74\" style=\"vertical-align: -6px;\"\/><\/li>\n<\/ol>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"aioseo-algorithm\">Algorithm<\/h4>\n\n\n\n<p>Given a initial guess of the root <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-c8700e0258243116de0d4f288e2e3b44_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#105;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"15\" style=\"vertical-align: -3px;\"\/>, the guess is updated <strong>iteratively<\/strong>: <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-d9a3592c730bc7274c0ac8127bef49dc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#123;&#105;&#43;&#49;&#125;&#32;&#61;&#32;&#103;&#40;&#120;&#95;&#105;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"94\" style=\"vertical-align: -5px;\"\/>.<\/p>\n\n\n\n<p>We also need a indicator to evaluate the convergence and to decide when to stop the iteration. The following error indicator serves this purpose:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 34px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-98b7cc0e7bf61acd5197f2587a7eaeed_l3.png\" height=\"34\" width=\"155\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#92;&#118;&#97;&#114;&#101;&#112;&#115;&#105;&#108;&#111;&#110;&#95;&#97;&#32;&#61;&#32;&#92;&#97;&#98;&#115;&#123;&#92;&#102;&#114;&#97;&#99;&#123;&#120;&#95;&#123;&#105;&#43;&#49;&#125;&#45;&#120;&#95;&#123;&#105;&#125;&#125;&#123;&#120;&#95;&#105;&#125;&#125;&#49;&#48;&#48;&#92;&#37;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"aioseo-convergence\">Convergence<\/h4>\n\n\n\n<p>One way to check whether the algorithm will yield convergent results is <strong>the two-curve graphical method<\/strong>.<\/p>\n\n\n\n<p>For the function <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-207ba33859b92ad7dd377a3a5c16b80b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#40;&#120;&#41;&#32;&#61;&#32;&#101;&#94;&#123;&#45;&#120;&#125;&#32;&#45;&#32;&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"117\" style=\"vertical-align: -5px;\"\/>, we rearrange into the form of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-0a4ea7609de170e52cd3fbf5173e80ed_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#101;&#94;&#123;&#45;&#120;&#125;&#32;&#61;&#32;&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"61\" style=\"vertical-align: 0px;\"\/>. If we plot <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-e70e5fc03572293a8532e7a7ee9631cd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#101;&#94;&#123;&#45;&#120;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"27\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-ede05c264bba0eda080918aaa09c4658_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/> respectively, then the intersection of the two curves represents the root we are looking for. The graph allows us the visualize the iterations as follows (It is easy to see that the algorithm converges!):<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"435\" height=\"417\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-33.png\" alt=\"\" class=\"wp-image-462\" style=\"width:364px;height:auto\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-33.png 435w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-33-300x288.png 300w\" sizes=\"auto, (max-width: 435px) 100vw, 435px\" \/><\/figure>\n\n\n\n<p>From this graphical perspective, we can also derive the <strong>sufficient condition<\/strong> for convergence is <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-6bcbfe34c987973cd8e4e314457ad39c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#97;&#98;&#115;&#123;&#103;&#39;&#40;&#120;&#41;&#125;&#32;&#60;&#32;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"69\" style=\"vertical-align: -5px;\"\/>. The following is the proof:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"250\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-34-1024x250.png\" alt=\"\" class=\"wp-image-465\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-34-1024x250.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-34-300x73.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-34-768x188.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-34.png 1153w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Note that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-96d8e3952f536616d4b9febe60b19e7c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#114;&#32;&#45;&#32;&#120;&#95;&#123;&#105;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"54\" style=\"vertical-align: -3px;\"\/> is the error for step <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-695d9d59bd04859c6c99e7feb11daab6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#105;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"6\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-01ae5c9e615aa3d94a27be95ec37f1fc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#114;&#32;&#45;&#32;&#120;&#95;&#123;&#105;&#43;&#49;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"71\" style=\"vertical-align: -5px;\"\/> is the error for step <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-6082c779f65a1a5899876fcd78a61e20_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#105;&#43;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"14\" width=\"36\" style=\"vertical-align: -2px;\"\/>. If we want the algorithm to converge, we want the error at step <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-6082c779f65a1a5899876fcd78a61e20_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#105;&#43;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"14\" width=\"36\" style=\"vertical-align: -2px;\"\/> smaller than the error at step <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-695d9d59bd04859c6c99e7feb11daab6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#105;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"6\" style=\"vertical-align: 0px;\"\/>. Hence, a <strong>sufficient<\/strong> condition for convergence is <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-6bcbfe34c987973cd8e4e314457ad39c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#97;&#98;&#115;&#123;&#103;&#39;&#40;&#120;&#41;&#125;&#32;&#60;&#32;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"69\" style=\"vertical-align: -5px;\"\/>.<\/p>\n\n\n\n<p>An offshoot of the analysis is that it also demonstrates that when<br>the method converges, the error is roughly proportional to and less<br>than the error of the previous step. For this reason, simple fixed-point<br>iteration is said to be <strong>linearly convergent<\/strong>. (Taken from textbook)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"aioseo-aitken-acceleration\">Aitken acceleration<\/h4>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"447\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-35-1024x447.png\" alt=\"\" class=\"wp-image-467\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-35-1024x447.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-35-300x131.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-35-768x336.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-35-1536x671.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-35.png 1689w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Aitken acceleration will improve the convergence speed from <strong>linear<\/strong> to <strong>quadratic<\/strong> in ideal condition (which satisfies the &#8221;geometric series&#8217; like assumption). <\/p>\n\n\n\n<p>We define:<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"97\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-36-1024x97.png\" alt=\"\" class=\"wp-image-468\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-36-1024x97.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-36-300x28.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-36-768x72.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-36.png 1241w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Then the acceleration scheme becomes:<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"756\" height=\"139\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-37.png\" alt=\"\" class=\"wp-image-469\" style=\"width:348px;height:auto\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-37.png 756w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-37-300x55.png 300w\" sizes=\"auto, (max-width: 756px) 100vw, 756px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"330\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-38-1024x330.png\" alt=\"\" class=\"wp-image-473\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-38-1024x330.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-38-300x97.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-38-768x247.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-38.png 1535w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-newton-raphson-method\">Newton-Raphson method<\/h3>\n\n\n\n<p>In fixed-point iteration, the only property from the target function is that local values of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-a7ee323bc5a3f73ad5e066b13bed5504_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#40;&#120;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"34\" style=\"vertical-align: -5px;\"\/> given a certain <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-ede05c264bba0eda080918aaa09c4658_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/>. Therefore, another direction to improve the convergence speed is trying to utilize more properties from the target function <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-a7ee323bc5a3f73ad5e066b13bed5504_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#40;&#120;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"34\" style=\"vertical-align: -5px;\"\/>. This is exactly what we do in the <strong>Newton-Raphson method<\/strong>, <\/p>\n\n\n\n<p>In the Newton-Raphson method, we use the information of <strong>derivatives<\/strong>. The following graph gives a good geometric intuition.<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"602\" height=\"514\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-39.png\" alt=\"\" class=\"wp-image-478\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-39.png 602w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-39-300x256.png 300w\" sizes=\"auto, (max-width: 602px) 100vw, 602px\" \/><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"aioseo-update-rule\">Update rule<\/h4>\n\n\n\n<p>The first derivative at <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-ede05c264bba0eda080918aaa09c4658_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/> is equivalent to the slope:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 42px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-1d7ca73811c7c1f90a01bb3987db1abc_l3.png\" height=\"42\" width=\"136\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#102;&#39;&#40;&#120;&#41;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#102;&#40;&#120;&#95;&#105;&#41;&#32;&#45;&#32;&#48;&#125;&#123;&#120;&#95;&#105;&#32;&#45;&#32;&#120;&#95;&#123;&#105;&#43;&#49;&#125;&#125;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>which can rearranged to yield:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 43px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-e4f337c1090291d37a9814c6f6bbd997_l3.png\" height=\"43\" width=\"141\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#120;&#95;&#123;&#105;&#43;&#49;&#125;&#32;&#61;&#32;&#120;&#95;&#123;&#105;&#125;&#32;&#45;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#102;&#40;&#120;&#95;&#105;&#41;&#125;&#123;&#102;&#39;&#40;&#120;&#95;&#123;&#105;&#125;&#41;&#125;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"aioseo-taylor-series\">Taylor series<\/h4>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"734\" height=\"942\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-40.png\" alt=\"\" class=\"wp-image-483\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-40.png 734w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-40-234x300.png 234w\" sizes=\"auto, (max-width: 734px) 100vw, 734px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"746\" height=\"930\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-41.png\" alt=\"\" class=\"wp-image-484\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-41.png 746w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-41-241x300.png 241w\" sizes=\"auto, (max-width: 746px) 100vw, 746px\" \/><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"aioseo-pitfalls\">Pitfalls<\/h4>\n\n\n\n<p>Just as every other open method, the Newton-Raphson method come with no guarantee of convergence. This diagram depicts the four common pitfalls that would lead to <strong>slow convergence\/divergence<\/strong> of the method.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>(a): <strong>Divergence<\/strong>: Inflection point in the vicinity of the root, i.e., <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-c30023c7ce88738e7685dbfc7d9c6f2a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#39;&#39;&#40;&#120;&#41;&#32;&#61;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"75\" style=\"vertical-align: -5px;\"\/><\/li>\n\n\n\n<li>(b): <strong>Root-jumping<\/strong>: Near-zero slope encounter<\/li>\n\n\n\n<li>(c): <strong>Oscillations<\/strong>: Iterations can oscillate around a local minima or maxim<\/li>\n\n\n\n<li>(d): <strong>Division-by-0<\/strong>: Zero slope<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"528\" height=\"883\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-42.png\" alt=\"\" class=\"wp-image-485\" style=\"width:381px;height:auto\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-42.png 528w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-42-179x300.png 179w\" sizes=\"auto, (max-width: 528px) 100vw, 528px\" \/><\/figure>\n\n\n\n<p>To deal with these potential pitfalls, we can:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Test with multiple initial values<\/li>\n\n\n\n<li>Adopt a hyperparameter <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-2b5c45836864531b8e37025dabadd24a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#97;&#109;&#98;&#100;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: 0px;\"\/> to scale the step (the &#8220;learning rate&#8221;): <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-54cfac36a902e6185fa265e8467ff166_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#123;&#107;&#43;&#49;&#125;&#32;&#61;&#32;&#120;&#95;&#107;&#32;&#45;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#102;&#40;&#120;&#95;&#107;&#41;&#125;&#123;&#102;&#39;&#40;&#120;&#95;&#107;&#41;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"29\" width=\"151\" style=\"vertical-align: -10px;\"\/><\/li>\n\n\n\n<li>And always remember to set the max iteration!<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-secant-method\">Secant method<\/h3>\n\n\n\n<p>The secant method is useful for the cases where the first-order derivatives cannot be computed analytically &#8211; a requirement for the Newton-Raphson method.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"aioseo-update-rule\">Update rule<\/h4>\n\n\n\n<p>Start with two values: <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-01a7b7b5dca66cb33a1207e1f39c1140_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"16\" style=\"vertical-align: -3px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-f1cd6be340b4fce14489cf5b565a169e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"17\" style=\"vertical-align: -3px;\"\/><\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"853\" height=\"250\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-43.png\" alt=\"\" class=\"wp-image-486\" style=\"width:392px;height:auto\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-43.png 853w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-43-300x88.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-43-768x225.png 768w\" sizes=\"auto, (max-width: 853px) 100vw, 853px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"724\" height=\"644\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-44.png\" alt=\"\" class=\"wp-image-488\" style=\"width:392px;height:auto\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-44.png 724w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-44-300x267.png 300w\" sizes=\"auto, (max-width: 724px) 100vw, 724px\" \/><\/figure>\n\n\n\n<p>You may find that the secant method is not that different from the Newton-Raphson method. Basically, it adopts additional estimation for the first order derivative.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"aioseo-polynomials\">Polynomials<\/h2>\n\n\n\n<p>To be honest, this section is considerably more complex but not complicated. I really don&#8217;t have energy to cover everything and I don&#8217;t find it fit to include too much details in the log. So please refer to the slides attached on this section.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-bairstows-method\">Bairstow&#8217;s method (for complex roots)<\/h3>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-quotient-difference-algorithm\">Quotient-Difference Algorithm<\/h3>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"aioseo-quadratic-interpolation\">Quadratic Interpolation<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-mullers-method\">Muller&#8217;s method<\/h3>\n\n\n\n<p>A quadratic interpolation method &#8211; using parabola to fit the curve (Compare with Newton-Raphson and false position &#8211; these are linear interpolation methods. The ideas are actually similiar.)<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"474\" height=\"454\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/03\/image-45.png\" alt=\"\" class=\"wp-image-490\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-45.png 474w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/03\/image-45-300x287.png 300w\" sizes=\"auto, (max-width: 474px) 100vw, 474px\" \/><\/figure>\n\n\n\n<p> <\/p>\n","protected":false},"excerpt":{"rendered":"<p>This log will focus on open methods for solving non-lin [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[37],"class_list":["post-440","post","type-post","status-publish","format-standard","hentry","category-math","tag-optimization"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/posts\/440","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/comments?post=440"}],"version-history":[{"count":38,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/posts\/440\/revisions"}],"predecessor-version":[{"id":493,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/posts\/440\/revisions\/493"}],"wp:attachment":[{"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/media?parent=440"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/categories?post=440"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/tags?post=440"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}