Newton's method กับการแก้สมการ

[Prisoners' Dilemma]

เป็นแบบฝึกหัดในหนังสือ Linear and Nonlinear Programming ของ Stephen Nash and Ariela Sofer อ่ะคับ ซึ่งไม่มีเฉลยอ่ะคับ เลยอยากให้ช่วย ๆ กันเฉลยกันหน่อยนะครับ
มี สองข้อ นะครับ

1. Let a be some positive constants. It's possible to use Newton's method to calculate 1/a to any desired accuracy without doing division. Determine a function f such that f(1/a)=0 and for which the formula for Newton's method only uses the arithmatic operations of addition, subtraction and multiplication. Determine all the ranges of initial points x0 for which the method converges.

2. Apply Newton's method to the system of nonlinear equations
f1(x1,x2) = x1^2+x2^2-1 = 0
f2(x1,x2) = 5x1^2-x2^2-2 = 0
There are four solutions to this system of equations. Can you find all four of them by using different initial guesses?

[Prisoners' Dilemma]

สำหรับ ข้อแรก ผมลองคิดมาบ้างแล้วครับ คือ
ให้ f(x) = a-(1/x) จะได้ f'(x)=1/x^2
จากสูตรนิวตันราฟสัน ก็ได้ ว่า
Xk+1 = Xk-(f(x)/f'(x)) ----> Xk+1 = Xk(2-aXk)

แต่มันจะยากตอน เลือกช่วงของ initial point X0 ที่ทำให้มันลู่เข้าอ่ะครับ
คือผมลองทำแล้ว กลัวได้ช่วงไม่ครบ

สำหรับข้อสอง จริง ๆ ถ้าทำตรง ๆ คือ หา Jacobian ก่อน ก็จะได้
แต่ก็มีจุดยากเหมือนกันคือการ มั่วค่า initial นี่แหละครับ
มันจะมั่วยังไงได้ตั้ง สี่ค่าที่ต่างกันอ่ะคับ

ขอคำชี้แนะด้วยครับ
~ Doosoyoroshiku ~

[passer-by]

ข้อ 1 ลองแก้อสมการ $ \left| g'(x_0)\right| < 1 $ ดูนะครับ มันเป็น sufficient condition ที่การันตีได้ว่า iterative process converges to the solution

อ้อ ! เกืือบลืม $g(x)$ มาจาก $ x_{k+1}= g(x_k) $

ส่วนข้อ 2 ผมเข้าใจครับว่า การหา initial guess ค่อนข้างจะโหดซักหน่อย ถึงแม้จะมี sufficient condition คล้ายๆข้อ 1 รองรับก็ตาม

ถ้าคิดแบบหยาบๆนะครับ ผมว่า ลองวาดรูปดููจุดตัด แล้วเลือก initial guess ที่ใกล้จุดตัดพวกนี้ ถ้าอยากได้แบบเร็วๆ ก็ต้องเสี่ยงดูครับ มันอาจจะมีสิทธิ์ converges แม้จะขัดกับ sufficient conditions

แต่ถ้าไม่ออก ก็คงต้องพึ่ง sufficient conditions และ rewrite สมการกันวุ่นวายเลยล่ะครับ

[Prisoners' Dilemma]

ขอบคุณมากครับ แต่ผมว่า เพราะมันเป็น sufficient condition รึเปล่าครับ ทำให้คำตอบที่ได้ไม่ครบ เพราะว่า
Xk+1 = g(X) = Xk(2-aXk) -> g'(x) = 2-2aXk ดังนั้น
|g'(x)| = |2-2aXk| < 1
แก้อสมการได้ 1/2a < Xk < 3/2a
แต่จริง ๆ แล้วผมว่า มันจะได้ช่วงที่กว้างกว่านี้ครับ คือ 0< X < 2/a อ่ะครับ

[M@gpie]

จากสูตรการวนซ้ำ Newton Raphson \[ x_{k+1} = x_k - \frac{f'(x_k)}{f(x_k)}\]
ให้ ${\displaystyle g(x)=x-\frac{f(x)}{f'(x)} } $ จะได้ว่า $ {\displaystyle g'(x) = \frac{f(x)f''(x)}{(f'(x))^2}}$
เราบังคับให้ $\left| \frac{f(x)f''(x)}{(f'(x))^2} \right| < 1$ ก็จะได้เงื่อนไขที่ต้องการครับ

ข้อสอง นี่ มั่วเอาครับ เพราะจริงๆแล้ว เราก็รู้อยู่ว่าแก้แล้วคำตอบคืออะไร

[passer-by]

ข้อความเดิมเขียนโดยคุณ Prisoners' Dilemma

เพราะมันเป็น sufficient condition รึเปล่าครับ ทำให้คำตอบที่ได้ไม่ครบ เพราะว่า
Xk+1 = g(X) = Xk(2-aXk) -> g'(x) = 2-2aXk ดังนั้น
|g'(x)| = |2-2aXk| < 1
แก้อสมการได้ 1/2a < Xk < 3/2a
แต่จริง ๆ แล้วผมว่า มันจะได้ช่วงที่กว้างกว่านี้ครับ คือ 0< X < 2/a อ่ะครับ

ครับ มันเป็นแค่ sufficient condition

ถ้าอยากได้ครบ ผมว่า สำหรับข้อนี้ อาจจะทำได้โดย วาดรูป พาราโบลาของ g(x) ตัดกับ y=x แล้ว iterate graphically บนช่วงนอกเหนือจาก sufficient condition ดูน่ะครับ

ถ้ามันวิ่งเข้าหาจุดตัดกราฟ ก็แสดงว่า converge

[Prisoners' Dilemma]

ขอบคุณคุณ passer by ครับ
ขอถามอีกอย่างนะครับ
ทำไมต้องตัดกับ y=x ด้วยครับ
เริ่มมึน ๆ แล้ว

[passer-by]

ข้อความเดิมเขียนโดยคุณ Prisoners' Dilemma

ขอถามอีกอย่างนะครับ
ทำไมต้องตัดกับ y=x ด้วยครับ

จากโจทย์ (Newton Method) เราใช้รูปแบบ iteration เป็น $ x_{k+1}= g(x_k) $

เมื่อ iterate มากขึ้น หรือ $ k \rightarrow \infty $ แล้ว LHS จะลู่เข้าสู่ Solution (สมมติเป็น x)

ส่วน RHS ก็จะลู่เข้า g(x)

เท่ากัับว่าตอนนี้ เราได้สมการ x = g(x)

ดังนั้น ถ้าอยากรู้ว่า x คืออะไร ก็ต้องหาจากจุดตัดกราฟ y = x และ y= g(x) ครับ