2.2 Newton’s Method#
Now we want to implement Newton’s method. For this, we utilize the first Taylor approximation (tangent) at the point \(x_n\):
Since we want to find the root, we set \(f(x_{n+1}) = 0\) and solve for \(x\):
The computational rule for the next \(x\) which is closer to the root is therefore iteratively invoked again and again. According to Newton’s method, the computational rule is:
We continue this until we have reached the desired accuracy, i.e., the desired distance from \(f(x_{n+1})\) to 0.
We thus need the first derivative of our function. We will calculate this manually for now:
import Pkg
Pkg.instantiate()
f(x) = -26 + 85 * x - 91 * x^2 + 44 * x^3 - 8 * x^4 + x^5
df(x) = 85 - 182 * x + 132 * x^2 - 32 * x^3 + 5 * x^4
df (generic function with 1 method)
Next, we require a function that calculates the distance from \(f(x_0)\) to 0, so that we know when we must terminate the process.
function dx(f, x)
return abs(0 - f(x))
end
dx (generic function with 1 method)
Now, the Newton method itself. We again provide the function, its derivative, and an initial value. Then we calculate the next value using the Newton method. We continue this process until we have reached the desired accuracy.
function newton(func, dfunc, x0, tolerance)
delta = dx(func, x0)
n = 0
while delta > tolerance
n += 1
x0 = x0 - func(x0) / dfunc(x0)
delta = dx(func, x0)
println("Iteration: ", n, " x0: ", x0)
if n > 100
break
end
end
return x0
end
newton (generic function with 1 method)
Let’s test our function with the initial value \(x_0 = 1\).
x = newton(f, df, 1.0, 0.0001)
println("x = ", x)
Iteration: 1 x0: 0.375
Iteration: 2 x0: 0.5159194399600385
Iteration: 3 x0: 0.5545080566547139
Iteration: 4 x0: 0.557015604236721
Iteration: 5 x0: 0.5570255161323902
x =
0.5570255161323902
For \(x_0 = 0\):
x = newton(f, df, 0.0, 0.0001)
println("x = ", x)
Iteration: 1 x0: 0.3058823529411765
Iteration: 2 x0: 0.4853190940239955
Iteration: 3 x0: 0.5496617287634946
Iteration: 4 x0: 0.5569412135377882
Iteration: 5 x0: 0.5570255051379259
x = 0.5570255051379259
And for \(x_0 = 5\).
x = newton(f, df, 5.0, 0.0001)
println("x = ", x)
Iteration: 1 x0: 3.9068750000000003
Iteration: 2 x0: 2.9968194172519835
Iteration: 3 x0: 2.2774066125543753
Iteration: 4 x0: 1.72766052390229
Iteration: 5 x0: 1.2684010520439337
Iteration: 6 x0: 0.7193102766389161
Iteration: 7 x0: 0.5090228763893254
Iteration: 8 x0: 0.5536227154224381
Iteration: 9 x0: 0.5570074263119684
Iteration: 10 x0: 0.5570255157731352
x = 0.5570255157731352
Newton’s Method with Arbitrary Functions#
We have already encountered the Taylor method and the package in Julia with which we can automatically compute the derivative. Let’s test this for our Newton’s method.
# Falls ihr das Package TaylorSeries noch nicht installiert habt, könnt ihr das hier tun
using Pkg
Pkg.add("TaylorSeries")
Updating registry at `~/.julia/registries/General.toml`
Resolving package versions...
No Changes to `~/.julia/environments/v1.8/Project.toml`
No Changes to `~/.julia/environments/v1.8/Manifest.toml`
using TaylorSeries # ansonsten fügen wir es einfach hinzu
We can compute the derivative using the package. Here’s an example call:
using TaylorSeries
func = x -> sin(x)
x = 1.0
TS = Taylor1(Float64, 1)
dfunc = func(TS)
ts = myFunc.(x)
Here, the Taylor polynomial at the point \(x_0=0\) is computed. We can also evaluate the polynomial at a different point. For this, we can utilize taylor_expand.
func_t = taylor_expand(func, a, order=1)
With the help of differentiate, we can calculate the derivative.
dfunc_t = differentiate(func_t)
First, create a function that constructs the Taylor series for a given function. The function should take the function as an argument and return the Taylor series.
function get_taylor(func, a)
func_t = taylor_expand(f, a, order=1) # Taylor series of f around a
return func_t
end
t_f = get_taylor(f, 0.5) # Taylor series of f around 0
- 1.21875 + 23.3125 t + 𝒪(t²)
We will now construct a Newton’s method that automatically calculates the derivative. Therefore, we only provide the function, the initial value, and the desired accuracy, this time without passing the derivative.
function newton_taylor(func, x0, tolerance)
func_t = get_taylor(func, x0)
delta = dx(func, x0)
n = 0
while delta > tolerance
n += 1
df_t = differentiate(func_t)
x0 = x0 - func(x0) / df_t()
delta = dx(func, x0)
func_t = get_taylor(func, x0)
println("Iteration: ", n, " x0: ", x0)
if n > 100
break
end
end
return x0
end
newton_taylor (generic function with 1 method)
x = newton_taylor(f, 1.0, 0.0001)
println("x = ", x)
Iteration: 1 x0: 0.375
Iteration: 2 x0: 0.5159194399600385
Iteration: 3 x0: 0.5545080566547139
Iteration: 4 x0: 0.557015604236721
Iteration: 5 x0: 0.5570255161323902
x = 0.5570255161323902