MATH256 2020–21 Numerical Methods (5 Parts)
Contents
3 Root finding algorithms 3-1
3.1 Errors in root finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-2
3.1.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-2
3.2 Testing for roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-2
3.3 The bisector method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-3
3.3.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-3
3.3.2 General method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-4
3.3.3 Convergence analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-4
3.3.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-5
3.4 The method of false position (regula falsi) . . . . . . . . . . . . . . . . . . . . . . . . . . 3-5
3.4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-6
3.5 The secant method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-7
3.6 The Newton–Raphson method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-7
3.6.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-8
3.6.2 Taylor series derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-9
3.7 Fixed point iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-9
3.7.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-10
3.8 Constructing fixed point schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-11
3.8.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-11
3.8.2 Example: Derivation of Newton–Raphson as a fixed point scheme . . . . . . . . . 3-12
3.9 The Newton–Raphson method in two dimensions . . . . . . . . . . . . . . . . . . . . . . 3-12
3.9.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-13
3.10 The Newton–Raphson method in n dimensions . . . . . . . . . . . . . . . . . . . . . . . 3-15
3.11 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-15
3.12 Final remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-16
* Download and save these files before reading on
§3.3 bisector.mw bisector_V1.mw
§3.4 false_position.mw false_position_V1.mw
§3.5 secant.mw secant_V1.mw
§3.6 newton_1d.mw newton_1d_V1.mw
§3.7 fixed_point.mw fixed_point_V1.mw
§3.9-3.10 newton_2d.mw, newton_3d.mw [OFXUPO@E@7NX]
3 Root finding algorithms
In this chapter, we consider the problem of solving the equation
f(x) = 0,
forarbitraryfunctionsf(x).WecansolvetheequationH(x)=kbydefiningG(x)=H(x)≠kandsolving
G(x)=0 TP UIF BCPWF OPUBUJPO JT HFOFSBM Manyproblems inappliedmathematicscanbe reduced to this
form,butthereare relatively fewcases inwhichanalyticsolutionsareavailable.
3-1
[V1 files contain more graphics]
