牛顿迭代法
Author : zbzhen, Modified : Wed Dec 25 19:43:47 2024
根据微分近似公式
f ( x ) ≈ f ( x 0 ) + ( x − x 0 ) f ′ ( x 0 ) f(x)\approx f(x_0)+(x-x_0)f'(x_0) f ( x ) ≈ f ( x 0 ) + ( x − x 0 ) f ′ ( x 0 )
如果f ( x ) = 0 f(x)=0 f ( x ) = 0
x ≈ x 0 − f ( x 0 ) f ′ ( x 0 ) x \approx x_0-\dfrac{f(x_0)}{f'(x_0)} x ≈ x 0 − f ′ ( x 0 ) f ( x 0 )
从而推得迭代公式
x ( n + 1 ) = x ( n ) − f ( x ( n ) ) f ′ ( x ( n ) ) x^{(n+1)}=x^{(n)}-\dfrac{f(x^{(n)})}{f'(x^{(n)})} x ( n + 1 ) = x ( n ) − f ′ ( x ( n ) ) f ( x ( n ) )
需要注意两点:
迭代公式的分母不能为零
若f f f f ′ ( x ( n ) ) f'(x^{(n)}) f ′ ( x ( n ) ) ∇ f \nabla f ∇ f
主要难点是多元问题, 除了可以简单的通过定义, 大部分情况下可以如下考虑:
直接通过例子说明:
f ( x , y ) = [ 2 x + 3 x y + 4 y x 2 + y 2 sin ( x y ) ] f(x,y) = \left[
\begin{array}{c}
2x+ 3xy + 4y \\
x^2 + y^2 \\
\sin(xy)
\end{array}
\right] f ( x , y ) = 2 x + 3 x y + 4 y x 2 + y 2 sin ( x y )
∇ f ( x , y ) = [ 2 + 3 y 3 x + 4 2 x 2 y y sin ( x y ) x sin ( x y ) ] \nabla f(x,y) = \left[
\begin{array}{c}
2 + 3y & 3x + 4 \\
2x & 2y\\
y\sin(xy) &x\sin(xy)\\
\end{array}
\right] ∇ f ( x , y ) = 2 + 3 y 2 x y sin ( x y ) 3 x + 4 2 y x sin ( x y )
通常并不会显示给出∇ f \nabla f ∇ f
∇ f [ u v ] = [ 2 + 3 y 3 x + 4 2 x 2 y y sin ( x y ) x sin ( x y ) ] [ u v ] = [ 2 u + 3 y u + 3 x v + 4 v 2 u x + 2 v y u y sin ( x y ) + v x sin ( x y ) ] \nabla f \begin{bmatrix}
u\\
v
\end{bmatrix}
= \left[
\begin{array}{c}
2 + 3y & 3x + 4 \\
2x & 2y\\
y\sin(xy) &x\sin(xy)\\
\end{array}
\right]
\begin{bmatrix}
u\\
v
\end{bmatrix} = \begin{bmatrix}
2u+3yu+3xv + 4v \\
2ux + 2vy \\
uy\sin(xy) +vx\sin(xy)\\
\end{bmatrix} ∇ f [ u v ] = 2 + 3 y 2 x y sin ( x y ) 3 x + 4 2 y x sin ( x y ) [ u v ] = 2 u + 3 y u + 3 xv + 4 v 2 ux + 2 v y u y sin ( x y ) + vx sin ( x y )
牛顿迭代求一元函数f ( x ) = x 2 − 2 f(x)=x^2-2 f ( x ) = x 2 − 2
def f ( x) :
return abs ( x* x - 2 )
def df ( x, h) :
return ( f( x+ h) - f( x) ) / h
def ite ( x, h) :
return x - f( x) / df( x, h)
x = 1
h = 0.001
for i in range ( 10 ) :
x = ite( x, h)
print ( x)
牛顿迭代求多元函数f ( x ) = [ 5 x 1 + 3 4 x 0 2 − 2 sin ( x 1 x 2 ) x 1 x 2 − 1.5 ] \bm f(\bm x)=
\begin{bmatrix}
5x_1+3\\
4x_0^2-2\sin(x_1x_2)\\
x_1x_2-1.5
\end{bmatrix} f ( x ) = 5 x 1 + 3 4 x 0 2 − 2 sin ( x 1 x 2 ) x 1 x 2 − 1.5
import numpy as np
def f ( x) :
x0, x1, x2 = x
ans= np. array( [ 5 * x1 + 3 , 4 * x0** 2 - 2 * np. sin( x1* x2) , x1* x2 - 1.5 ] )
return ans
def df ( x, h= 0.00001 ) :
x = x[ : , None ]
hmpx = x + np. eye( len ( x) ) * h
ans = np. array( f( hmpx) - f( x) ) / h
return ans
def ite ( x, h) :
return x - np. linalg. solve( df( x, h) , f( x) )
x = np. array( [ 2 , 2 , - 2 ] )
h = 0.000001
for i in range ( 10 ) :
x = ite( x, h)
print ( x)
print ( f( x) )