Page - 181 - in Programming for Computations – Python - A Gentle Introduction to Numerical Simulations with Python 3.6, Volume Second Edition

7.2 Newton’sMethod 181 WhatIs theDifferenceBetween Linear andNonlinearEquations? You know how to solve linear equationsax+b = 0: x = −b/a. All other types of equationsf(x) = 0, i.e., when f(x) is not a linear function of x, are called nonlinear. A typical way of recognizing a nonlinear equation is to observe that x is “not alone” as in ax, but involved in a product with itself, suchas inx3+2x2−9=0.We say thatx3 and2x2 arenonlinear terms.An equationlikesinx+excosx=0isalsononlinearalthoughx isnotexplicitly multiplied by itself, but the Taylor series of sinx, ex, and cosx all involve polynomialsofxwherex ismultipliedby itself. 7.2 Newton’sMethod Newton’s method, also known as Newton-Raphson’smethod, is a very famous and widely used method for solving nonlinear algebraic equations.1 Compared to the othermethodspresented in thischapter, i.e., secantandbisection, it isgenerally the fastest one (although computational speed rarely is an issue with a single equation onmodern laptops).However, it doesnotguaranteethatanexistingsolutionwillbe found. Afundamental ideaofnumericalmethodsfornonlinearequations is toconstruct a seriesof linearequations(sinceweknowhowtosolve linearequations)andhope that thesolutionsof these linearequationsbringuscloserandcloser to the solution of the nonlinear equation. The idea will be clearer when we present Newton’s methodand thesecantmethod. 7.2.1 DerivingandImplementingNewton’sMethod Figure 7.1 shows thef(x) function in our model equationx2 −9 = 0. Numerical methods for algebraic equations require us to guess at a solution first. Here, this guess is called x0. The fundamental idea of Newton’s method is to approximate the original function f(x) by a straight line, i.e., a linear function, since it is straightforward to solve linear equations.There are infinitely many choices of how toapproximatef(x)byastraightline.Newton’smethodappliesthetangentoff(x) atx0, see therightmost tangentinFig.7.1.This linear tangentfunctioncrosses thex axis at a pointwe callx1. This is (hopefully)a better approximation to the solution off(x)= 0 thanx0. The next fundamental idea is to repeat this process. We find the tangent of f at x1, compute where it crosses the x axis, at a point called x2, andrepeat theprocessagain.Figure7.1shows that theprocessbringsuscloserand closer to the left. It remains, however, to see if we hit x = 3 or come sufficiently close to this solution. 1 ReadmoreaboutNewton’smethod,e.g.,onhttps://en.wikipedia.org/wiki/Newton%27s_method.