คำตอบของระบบไม่เชิงเส้นที่ง่ายที่สุด วิธีการวนซ้ำอย่างง่ายสำหรับการแก้ระบบสมการเชิงเส้น (สลาฟ) วิธีการของนิวตัน: รากฐานทางทฤษฎี
การแก้สมการไม่เชิงเส้น
สมมติว่าเราจำเป็นต้องแก้สมการ
ที่ไหน
– ฟังก์ชันต่อเนื่องไม่เชิงเส้น
วิธีการแก้สมการแบ่งออกเป็นแบบตรงและแบบวนซ้ำ วิธีการทางตรงคือวิธีการที่ช่วยให้คุณคำนวณหาคำตอบโดยใช้สูตรได้ (เช่น การหารากของสมการกำลังสอง) วิธีการวนซ้ำคือวิธีการที่ระบุการประมาณเริ่มต้นบางอย่าง และสร้างลำดับการบรรจบกันของการประมาณกับผลลัพธ์ที่แน่นอน โดยแต่ละการประมาณที่ตามมาจะถูกคำนวณโดยใช้วิธีก่อนหน้า
แนวทางแก้ไขปัญหาที่สมบูรณ์สามารถแบ่งออกเป็น 3 ขั้นตอน:
กำหนดจำนวน ลักษณะ และตำแหน่งของรากของสมการ (1)
ค้นหาค่าประมาณของรากเช่น ระบุช่วงเวลาที่รากจะงอก (แยกราก)
ค้นหาค่าของรากด้วยความแม่นยำที่ต้องการ (ระบุราก)
มีวิธีการวิเคราะห์และกราฟิกที่หลากหลายสำหรับการแก้ปัญหาสองข้อแรก
วิธีการที่ชัดเจนที่สุดในการแยกรากของสมการ (1) คือการกำหนดพิกัดของจุดตัดของกราฟของฟังก์ชัน
กับแกนแอบซิสซา แอบซิสซาส จุดตัดกราฟ
มีเพลา
คือรากของสมการ (1)
ช่วงการแยกสำหรับรากของสมการ (1) สามารถหาได้ในเชิงวิเคราะห์ โดยขึ้นอยู่กับทฤษฎีบทเกี่ยวกับคุณสมบัติของฟังก์ชันที่ต่อเนื่องในช่วงเวลาหนึ่ง
เช่น ถ้าเป็นฟังก์ชัน
อย่างต่อเนื่องในส่วนนี้
และ
จากนั้นตามทฤษฎีบทโบลซาโน–คอชีในส่วนนี้
มีอย่างน้อยหนึ่งรากของสมการ (1) (เป็นจำนวนคี่)
ถ้าฟังก์ชั่น
เป็นไปตามเงื่อนไขของทฤษฎีบทโบลซาโน-คอชี และเป็นแบบโมโนโทนิคในช่วงเวลานี้ จากนั้น
มีรากของสมการ (1) เพียงรากเดียว ดังนั้นสมการ (1) จึงมี
รูตเดียวหากตรงตามเงื่อนไขต่อไปนี้:
หากฟังก์ชันสามารถหาอนุพันธ์ได้อย่างต่อเนื่องในช่วงเวลาที่กำหนด เราสามารถใช้ข้อพิสูจน์จากทฤษฎีบทของโรล ซึ่งจะมีจุดคงที่อย่างน้อยหนึ่งจุดระหว่างรากคู่หนึ่งเสมอ อัลกอริทึมสำหรับการแก้ปัญหาในกรณีนี้จะเป็นดังนี้:
เครื่องมือที่มีประโยชน์สำหรับการแยกรากก็คือการใช้ทฤษฎีบทของสตวร์ม
การแก้ปัญหาที่สามดำเนินการโดยวิธีการวนซ้ำ (ตัวเลข) ต่างๆ: วิธีไดโคโตมี, วิธีวนซ้ำอย่างง่าย, วิธีของนิวตัน, วิธีคอร์ด ฯลฯ
ตัวอย่างมาแก้สมการกัน
วิธี การวนซ้ำอย่างง่าย. มาตั้งค่ากัน
. มาสร้างกราฟของฟังก์ชันกัน
กราฟแสดงว่ารากของสมการของเราอยู่ในส่วนนั้น
, เช่น.
คือส่วนที่แยกออกจากรากของสมการของเรา ลองตรวจสอบสิ่งนี้เชิงวิเคราะห์เช่น การปฏิบัติตามเงื่อนไข (2):
ขอให้เราระลึกว่าสมการดั้งเดิม (1) ในวิธีการวนซ้ำอย่างง่ายถูกแปลงเป็นรูปแบบ
และการวนซ้ำจะดำเนินการตามสูตร:
(3)
การคำนวณโดยใช้สูตร (3) เรียกว่าการวนซ้ำหนึ่งครั้ง การวนซ้ำจะหยุดเมื่อตรงตามเงื่อนไข
, ที่ไหน - ข้อผิดพลาดแน่นอนในการค้นหารูทหรือ
, ที่ไหน -ข้อผิดพลาดที่เกี่ยวข้อง
วิธีการวนซ้ำอย่างง่ายจะมาบรรจบกันหากตรงตามเงื่อนไข
สำหรับ
. การเลือกฟังก์ชั่น
ในสูตร (3) สำหรับการวนซ้ำ คุณสามารถมีอิทธิพลต่อการลู่เข้าของวิธีการได้ ในกรณีที่ง่ายที่สุด
ด้วยเครื่องหมายบวกหรือลบ
ในทางปฏิบัติก็มักจะแสดงออกมา
โดยตรงจากสมการ (1) หากไม่ตรงตามเงื่อนไขการลู่เข้า ให้แปลงเป็นรูปแบบ (3) แล้วเลือก ลองแสดงสมการของเราในรูปแบบ
(แสดง x จากสมการ) ลองตรวจสอบเงื่อนไขการบรรจบกันของวิธีการนี้:
สำหรับ
. โปรดทราบว่าเงื่อนไขการลู่เข้าไม่เป็นที่พอใจ
ดังนั้นเราจึงใช้ส่วนของการแยกราก
. ในการผ่านเราสังเกตว่าเมื่อนำเสนอสมการของเราในรูปแบบ
ไม่เป็นไปตามเงื่อนไขการบรรจบกันของวิธีการ:
บนส่วน
. กราฟแสดงให้เห็นว่า
เพิ่มขึ้นเร็วกว่าฟังก์ชัน
(|tg| มุมเอียงของเส้นสัมผัสกันถึง
บนส่วน
)
มาเลือกกัน
. เราจัดระเบียบการวนซ้ำตามสูตร:
เราจัดระเบียบกระบวนการวนซ้ำโดยทางโปรแกรมด้วยความแม่นยำที่กำหนด:
> fv:=proc(f1,x0,eps)
> เค:=0:
x:=x1+1:
ในขณะที่ abs(x1-x)> eps ทำ
x1:=f1(x):
พิมพ์ (ประเมิน (x1,8)):
พิมพ์(เอบีเอส(x1-x)):
:printf("จำนวน iter.=%d ",k):
จบ:
เมื่อวนซ้ำ 19 เราได้รากของสมการแล้ว
ด้วยความผิดพลาดโดยสิ้นเชิง
มาแก้สมการของเรากัน วิธีการของนิวตัน. การวนซ้ำในวิธีของนิวตันดำเนินการตามสูตร:
วิธีของนิวตันถือได้ว่าเป็นวิธีการวนซ้ำอย่างง่ายด้วยฟังก์ชัน จากนั้นเงื่อนไขสำหรับการลู่เข้าของวิธีของนิวตันจะถูกเขียนเป็น:
.
ในสัญกรณ์ของเรา
และเงื่อนไขการลู่เข้าเป็นไปตามช่วง
ดังที่เห็นบนกราฟ:
โปรดจำไว้ว่าวิธีการของนิวตันมาบรรจบกันที่อัตรากำลังสองและการประมาณเริ่มต้นจะต้องเลือกให้ใกล้กับรากอย่างเพียงพอ มาคำนวณกัน:
, การประมาณเบื้องต้น, . เราจัดระเบียบการวนซ้ำตามสูตร:
เราจัดระเบียบกระบวนการวนซ้ำโดยทางโปรแกรมด้วยความแม่นยำที่กำหนด ในการวนซ้ำที่ 4 เราจะได้รากของสมการ
กับ
เราดูวิธีการแก้สมการไม่เชิงเส้นโดยใช้สมการลูกบาศก์เป็นตัวอย่าง โดยธรรมชาติแล้ว วิธีเหล่านี้จะแก้สมการไม่เชิงเส้นประเภทต่างๆ เช่น การแก้สมการ
วิธีการของนิวตันด้วย
ให้หารากของสมการที่ [-1.5;-1]:
ออกกำลังกาย: แก้สมการไม่เชิงเส้นได้อย่างแม่นยำ
0.
การแบ่งส่วนออกครึ่งหนึ่ง (dichotomy)
การวนซ้ำอย่างง่าย
นิวตัน (แทนเจนต์)
ซีแคนต์ - คอร์ด
ตัวเลือกงานคำนวณดังนี้: ตัวเลขในรายการหารด้วย 5 (
) ส่วนจำนวนเต็มสอดคล้องกับหมายเลขสมการ ส่วนที่เหลือคือหมายเลขวิธี
งานห้องปฏิบัติการหมายเลข 3-4
ตัวเลือก #5
เป้าหมายของงาน:เรียนรู้การแก้ระบบสมการไม่เชิงเส้น (SNE) โดยใช้วิธีวนซ้ำอย่างง่าย (SI) และวิธีการของนิวตันโดยใช้คอมพิวเตอร์
1. ศึกษาวิธี MPI และวิธีการของนิวตันในการแก้ระบบสมการไม่เชิงเส้น
2. ใช้ตัวอย่างเฉพาะ เรียนรู้ขั้นตอนการแก้ระบบสมการไม่เชิงเส้นด้วย MPI และวิธีการของนิวตันโดยใช้คอมพิวเตอร์
3. สร้างโปรแกรมและใช้แก้ระบบสมการด้วยความแม่นยำ .
ตัวอย่างประสิทธิภาพการทำงาน
ออกกำลังกาย.
1. แก้ปัญหา SNE ในเชิงวิเคราะห์:
2. สร้างสูตรการทำงานของ MPI และวิธีการของนิวตันสำหรับการแก้ปัญหาเชิงตัวเลขของระบบที่การประมาณเริ่มต้น:
3. เขียนโปรแกรมในภาษาการเขียนโปรแกรมใดๆ ที่ใช้กระบวนการวนซ้ำที่สร้างขึ้น
สารละลาย.
วิธีการวิเคราะห์
โซลูชันการวิเคราะห์ของ SDE คือจุด และ
วิธีการวนซ้ำอย่างง่าย (SIM)
ในการสร้างสูตร MPI ที่ใช้งานได้สำหรับการแก้ปัญหาเชิงตัวเลขของระบบ ขั้นแรกจำเป็นต้องนำมาไว้ในแบบฟอร์ม:
เมื่อต้องการทำเช่นนี้ ให้คูณสมการแรกของระบบด้วยค่าคงที่ที่ไม่รู้จัก สมการที่สองด้วย จากนั้นบวกเข้าด้วยกันแล้วบวกเข้ากับทั้งสองด้านของสมการ เราได้รับสมการแรกของระบบที่ถูกแปลง:
เรากำหนดค่าคงที่ที่ไม่รู้จักจากเงื่อนไขที่เพียงพอสำหรับการลู่เข้าของกระบวนการวนซ้ำ:
มาเขียนเงื่อนไขเหล่านี้โดยละเอียด:
สมมติว่านิพจน์ภายใต้เครื่องหมายมอดุลัสเท่ากับศูนย์ เราจะได้ระบบสมการพีชคณิตเชิงเส้น (SLAE) ลำดับที่ 4 โดยไม่ทราบค่า 4 ตัว:
เพื่อแก้ระบบจำเป็นต้องคำนวณอนุพันธ์บางส่วน:
จากนั้น SLAE จะถูกเขียนดังนี้:
โปรดทราบว่าหากอนุพันธ์ย่อยเปลี่ยนแปลงเพียงเล็กน้อยในบริเวณใกล้เคียงกับการประมาณเริ่มต้น ดังนั้น:
จากนั้น SLAE จะถูกเขียนดังนี้:
คำตอบของระบบนี้คือจุด , , , . จากนั้นสูตรการทำงานของ MPI ในการแก้ SNL จะอยู่ในรูปแบบ:
สำหรับการใช้งานบนคอมพิวเตอร์สามารถเขียนสูตรการทำงานใหม่ได้ดังนี้:
กระบวนการวนซ้ำสามารถเริ่มต้นได้โดยการตั้งค่าการประมาณเริ่มต้น x 0 =-2, y 0 =-4 กระบวนการจะสิ้นสุดเมื่อตรงตามเงื่อนไขสองข้อพร้อมกัน: และ ในกรณีนี้ค่าและเป็นค่าโดยประมาณของหนึ่งในคำตอบของ SNL
วิธีการของนิวตัน
เพื่อสร้างสูตรการทำงานสำหรับวิธีของนิวตันในรูปแบบ
โดยที่ จำเป็น:
1. ค้นหาเมทริกซ์ของอนุพันธ์ย่อย:
2. ค้นหาดีเทอร์มิแนนต์ของเมทริกซ์นี้:
3. กำหนดเมทริกซ์ผกผัน:
หลังจากทำการเปลี่ยนแปลงแล้ว:
เราได้รับสูตรการทำงานของวิธีของนิวตันสำหรับการใช้งานบนคอมพิวเตอร์:
บล็อกไดอะแกรมวิธีการแก้ SLE ของ MPI และนิวตันแสดงไว้ในรูปที่ 1
รูปที่ 1 แบบแผนของ MPI และวิธีการของนิวตัน
ข้อความโปรแกรม:
โปรแกรม P3_4; (การวนซ้ำ)
ใช้ Crt;
var n: จำนวนเต็ม;
clrscr;
xn:=x-(x-y+2)+(1/2)*(x*y-3);
yn:=y+(2/3)*(x-y+2)+(1/6)*(x*y-3);
writeln (n:3, x:9:5, xn:9:5, (xn-x):9:5, y:9:5, yn:9:5, (yn-y):9:5) ;
น:=n+1;
จนกระทั่ง (abs(x-zx)<=eps) and (abs(y-zy)<=eps);
อ่าน;
2) วิธีการของนิวตัน:
โปรแกรม P3_4; (นิวตัน)
ใช้ Crt;
var n: จำนวนเต็ม;
x0,x,xn,y0,y,yn,eps,zx,zy:จริง;
clrscr;
น:=0; x0:=-2; x:=x0; ย0:=-4; ย:=y0; อัตรากำไรต่อหุ้น:=0.001;
writeln(" n x(i) x(i+1) x(i+1)-x(i) y(i) y(i+1) y(i+1)-y(i) ");
xn:=x-(1/(x+y))*(x*x-x*y+2*x+x-y+2);
yn:=y-(1/(x+y))*(x*y*(-y)-3*(-y)+x*y-3);
writeln (n:3, x:9:5, xn:9:5, abs(xn-x):9:5, y:9:5, yn:9:5, abs(yn-y):9: 5);
น:=n+1;
จนกระทั่ง (abs(x-zx)<=eps) and (abs(y-zy)<=eps);
ผลลัพธ์การรันโปรแกรม:
· รูปที่ 2 – โปรแกรมที่ทำงานโดยใช้วิธีการวนซ้ำอย่างง่าย
· รูปที่ 3 – โปรแกรมที่ทำงานตามวิธีของนิวตัน
รูปที่ 2 คำตอบ: x(16)ñ-3.00023, y(16)ñ-1.00001
รูปที่ 3 คำตอบ: x(8)ñ-3.00000, y(8)ñ-1.00000
โดยธรรมชาติแล้วทุกคนแสวงหาความรู้ (อริสโตเติล อภิปรัชญา)
วิธีการเชิงตัวเลข: การแก้สมการไม่เชิงเส้น
ปัญหาในการแก้สมการเกิดขึ้นอย่างต่อเนื่องในทางปฏิบัติ เช่น ในทางเศรษฐศาสตร์ เมื่อพัฒนาธุรกิจ คุณต้องการทราบว่าเมื่อใดที่ผลกำไรจะถึงมูลค่าที่แน่นอน ในทางการแพทย์ เมื่อศึกษาผลกระทบของยา สิ่งสำคัญคือต้องรู้ว่าเมื่อความเข้มข้น ของสารก็จะถึงระดับที่กำหนด เป็นต้น
ในปัญหาการหาค่าเหมาะที่สุด มักจำเป็นต้องกำหนดจุดที่อนุพันธ์ของฟังก์ชันกลายเป็น 0 ซึ่งเป็นเงื่อนไขที่จำเป็น ท้องถิ่นสุดขั้ว
ในสถิติ เมื่อสร้างการประมาณโดยใช้กำลังสองน้อยที่สุดหรือวิธีความน่าจะเป็นสูงสุด คุณจะต้องแก้สมการไม่เชิงเส้นและระบบสมการด้วย
ดังนั้นปัญหาทั้งระดับจึงเกิดขึ้นที่เกี่ยวข้องกับการค้นหาวิธีแก้ไข ไม่เชิงเส้นสมการ เช่น สมการหรือสมการ เป็นต้น
ในกรณีที่ง่ายที่สุด เรามีฟังก์ชันที่กำหนดไว้ในช่วงเวลา ( ก, b ) และรับค่าบางอย่าง
แต่ละค่า x จากส่วนนี้เราสามารถเปรียบเทียบจำนวนได้นี่คือ การทำงานการพึ่งพาอาศัยกันซึ่งเป็นแนวคิดหลักในวิชาคณิตศาสตร์
เราจำเป็นต้องค้นหาค่าซึ่งเรียกว่ารากของฟังก์ชัน
เราต้องกำหนดจุดตัดของกราฟฟังก์ชันด้วยสายตากับแกนแอบซิสซา
วิธีการลดลงครึ่งหนึ่ง
วิธีที่ง่ายที่สุดในการค้นหารากของสมการคือวิธีการแบ่งครึ่งหรือ ขั้ว.
วิธีนี้ใช้งานง่ายและทุกคนก็จะปฏิบัติในลักษณะเดียวกันเมื่อแก้ไขปัญหา
อัลกอริธึมมีดังนี้
สมมติว่าเราพบสองจุด และ เพื่อให้พวกเขามี แตกต่างสัญญาณ จากนั้นจะมีรากของฟังก์ชันอย่างน้อยหนึ่งรายการระหว่างจุดเหล่านี้
แบ่งส่วนออกครึ่งหนึ่งแล้วเข้าไป เฉลี่ยจุด .
แล้วอย่างใดอย่างหนึ่ง , หรือ .
ปล่อยให้ครึ่งหนึ่งของส่วนที่ค่าที่ส่วนท้ายมีเครื่องหมายต่างกัน ตอนนี้เราแบ่งส่วนนี้ออกครึ่งหนึ่งอีกครั้งและปล่อยให้ส่วนนั้นอยู่ในขอบเขตที่ฟังก์ชันมีสัญญาณที่แตกต่างกันและอื่น ๆ เพื่อให้ได้ความแม่นยำที่ต้องการ
แน่นอนว่าเราจะค่อยๆ จำกัดพื้นที่ซึ่งเป็นที่ตั้งของรากของฟังก์ชันให้แคบลง และด้วยเหตุนี้ เราจะกำหนดมันด้วยความแม่นยำระดับหนึ่ง
โปรดทราบว่าอัลกอริทึมที่อธิบายไว้นั้นใช้ได้กับฟังก์ชันต่อเนื่องใดๆ
ข้อดีของวิธีการแบ่งครึ่งคือความน่าเชื่อถือและความเรียบง่ายสูง
ข้อเสียของวิธีนี้คือก่อนที่คุณจะเริ่มใช้งานคุณจะต้องค้นหาจุดสองจุดโดยที่ค่าฟังก์ชันมีเครื่องหมายต่างกัน เห็นได้ชัดว่าวิธีนี้ใช้ไม่ได้กับรากที่มีหลายหลากเท่ากัน และไม่สามารถสรุปได้ทั่วไปในกรณีของรากที่ซับซ้อนและระบบสมการ
ลำดับของการบรรจบกันของวิธีการเป็นแบบเส้นตรง ในแต่ละขั้นตอนความแม่นยำจะเพิ่มขึ้นเป็นสองเท่า ยิ่งทำซ้ำมากเท่าใด รากก็จะยิ่งแม่นยำมากขึ้นเท่านั้น
วิธีการของนิวตัน: รากฐานทางทฤษฎี
วิธีการคลาสสิกของนิวตันหรือ แทนเจนต์ก็คือถ้าเป็นการประมาณค่ารากของสมการ จากนั้นการประมาณถัดไปจะถูกกำหนดให้เป็นรากของแทนเจนต์ของฟังก์ชันที่วาดที่จุด
สมการแทนเจนต์ของฟังก์ชัน ณ จุดหนึ่งจะมีรูปแบบดังนี้
ในสมการแทนเจนต์เราใส่ และ .
จากนั้นอัลกอริทึมสำหรับการคำนวณตามลำดับในวิธีของนิวตันจะเป็นดังนี้:
การลู่เข้าของวิธีแทนเจนต์เป็นแบบกำลังสอง ลำดับของการลู่เข้าคือ 2
ดังนั้นการบรรจบกันของวิธีแทนเจนต์ของนิวตันจึงรวดเร็วมาก
จำความจริงอันมหัศจรรย์นี้ไว้!
โดยไม่มีการเปลี่ยนแปลงใดๆ วิธีการจะมีลักษณะทั่วไปสำหรับกรณีที่ซับซ้อน
ถ้ารากเป็นรากของการทวีคูณที่สองหรือสูงกว่า ลำดับของการบรรจบกันจะลดลงและกลายเป็นเส้นตรง
แบบฝึกหัดที่ 1. ใช้วิธีแทนเจนต์ หาคำตอบของสมการในส่วน (0, 2)
แบบฝึกหัดที่ 2ใช้วิธีแทนเจนต์ หาคำตอบของสมการในส่วน (1, 3)
ข้อเสียของวิธีของนิวตันรวมถึงบริเวณนั้นด้วย เนื่องจากรับประกันว่าจะมาบรรจบกันเพื่อการประมาณเริ่มต้นโดยพลการก็ต่อเมื่อเงื่อนไขเป็นที่พอใจทุกที่ ในสถานการณ์ตรงกันข้าม การบรรจบกันเกิดขึ้นเฉพาะในพื้นที่ใกล้เคียงของรากเท่านั้น
ข้อเสียของวิธีของนิวตันคือต้องคำนวณอนุพันธ์ในแต่ละขั้นตอน
การแสดงวิธีของนิวตัน
วิธีของนิวตัน (วิธีแทนเจนต์) จะใช้ถ้าสมการ ฉ(x) = 0 มีรากและตรงตามเงื่อนไขต่อไปนี้:
1) ฟังก์ชั่น ย= ฉ(x) กำหนดและต่อเนื่องที่ ;
2) ฉ(ก)· ฉ(ข) < 0 (ฟังก์ชันรับค่าของเครื่องหมายต่าง ๆ ที่ส่วนท้ายของเซ็กเมนต์ [ ก; ข]);
3) อนุพันธ์ ฉ"(x) และ ฉ""(x) รักษาเครื่องหมายไว้ตามช่วงเวลา [ ก; ข] (เช่น function ฉ(x) เพิ่มขึ้นหรือลดลงในส่วน [ ก; ข] โดยยังคงรักษาทิศทางของความนูน)
แนวคิดหลักของวิธีการมีดังนี้: ในส่วน [ ก; ข] มีการเลือกหมายเลขดังกล่าว x 0 , ที่ที่ ฉ(x 0 ) มีเครื่องหมายเดียวกันกับ ฉ"" (x 0 ), นั่นคือเงื่อนไขเป็นที่พอใจ ฉ(x 0 )· ฉ"" (x) > 0 . ดังนั้นจึงเลือกจุดที่มี abscissa x 0 ซึ่งแทนเจนต์กับเส้นโค้ง ย= ฉ(x) บนส่วน [ ก; ข] ตัดแกน วัว. ต่อจุด x 0 ขั้นแรก สะดวกในการเลือกปลายด้านใดด้านหนึ่งของเซ็กเมนต์
ลองพิจารณาวิธีของนิวตันโดยใช้ตัวอย่างเฉพาะ
ให้เราได้รับฟังก์ชันเพิ่มขึ้น y = ฉ(x) = x 2 -2,ต่อเนื่องในส่วน (0;2) และมี ฉ"(เอ็กซ์) = 2 x > 0 และ ฉ "" (x) = 2 > 0 .
การวาดภาพ1 . ฉ(x) =x 2 -2
สมการแทนเจนต์ในรูปแบบทั่วไปมีการแสดงดังต่อไปนี้:
ป-ป 0 = ฉ" (x 0)·(x-x 0)
ในกรณีของเรา: ปปป 0 =2x 0 ·(x-x 0)สำหรับจุด x 0 เราเลือกจุด ข 1 (ข; ฉ(ข)) = (2,2)วาดแทนเจนต์ให้กับฟังก์ชัน ย = ฉ(x)ที่จุด B 1 และแสดงถึงจุดตัดของเส้นสัมผัสกันและแกน วัวจุด x1. เราได้สมการของแทนเจนต์แรก: y-2=2·2(x-2), y=4x-6
อ็อกซ์: x 1 =
การวาดภาพ2. ผลลัพธ์ของการทำซ้ำครั้งแรก
y=ฉ(x) วัวผ่านจุด x1เราเข้าใจประเด็นแล้ว ข 2 =(1.5; 0.25). วาดแทนเจนต์ให้กับฟังก์ชันอีกครั้ง ย = ฉ(x)ที่จุด B 2 และแสดงถึงจุดตัดของเส้นสัมผัสกันและแกน วัวจุด x2.
สมการของแทนเจนต์ที่สอง: ย-0.25=2*1.5(x-1.5), ย = 3 x - 4.25.
จุดตัดของแทนเจนต์และแกน อ็อกซ์: x 2 =.
การวาดภาพ3. การทำซ้ำวิธีของนิวตันครั้งที่สอง
จากนั้นเราจะหาจุดตัดของฟังก์ชัน y=ฉ(x)และตั้งฉากกับแกน วัวผ่านจุด x 2 เราจะได้จุด B 3 ไปเรื่อยๆ
การวาดภาพ4. ขั้นตอนที่สามของวิธีแทนเจนต์
การประมาณรากครั้งแรกถูกกำหนดโดยสูตร:
= 1.5.
การประมาณรากที่สองถูกกำหนดโดยสูตร:
=
การประมาณรากที่สามถูกกำหนดโดยสูตร:
ดังนั้น , ฉันการประมาณรากครั้งที่ 2 ถูกกำหนดโดยสูตร:
การคำนวณจะดำเนินการจนกระทั่งถึงตำแหน่งทศนิยมที่จำเป็นในการจับคู่คำตอบหรือบรรลุความแม่นยำที่ระบุ e - จนกว่าความไม่เท่าเทียมกันจะเป็นที่พอใจ | ซี- ซี-1 | < จ.
ในกรณีของเรา ลองเปรียบเทียบค่าประมาณที่ได้รับในขั้นตอนที่สามกับคำตอบจริงที่คำนวณด้วยเครื่องคิดเลข:
รูปที่ 5 รากของ 2 คำนวณจากเครื่องคิดเลข
อย่างที่คุณเห็นในขั้นตอนที่สามเราได้รับข้อผิดพลาดน้อยกว่า 0.000002
ด้วยวิธีนี้ คุณสามารถคำนวณค่าของค่า "รากที่สองของ 2" ได้อย่างแม่นยำในระดับใดก็ได้ วิธีการอันน่าทึ่งนี้คิดค้นโดยนิวตัน และช่วยให้คุณค้นหารากของสมการที่ซับซ้อนมากได้
วิธีการของนิวตัน: แอปพลิเคชันใน C ++
ในบทความนี้ เราจะทำให้กระบวนการคำนวณรากของสมการเป็นแบบอัตโนมัติโดยการเขียนแอปพลิเคชันคอนโซลใน C++ เราจะพัฒนามันใน Visual C++ 2010 Express ซึ่งเป็นสภาพแวดล้อมการพัฒนา C++ ฟรีและสะดวกมาก
ก่อนอื่น มาเปิดตัว Visual C++ 2010 Express กันก่อน หน้าต่างเริ่มโปรแกรมจะปรากฏขึ้น ที่มุมซ้ายคลิก "สร้างโครงการ"
ข้าว. 1. หน้าแรกของ Visual C++ 2010 Express
ในเมนูที่ปรากฏขึ้น ให้เลือก "แอปพลิเคชันคอนโซล Win32" และป้อนชื่อแอปพลิเคชัน "Newton_Method"
ข้าว. 2. สร้างโครงการ
// วิธีการ Newton.cpp: กำหนดจุดเริ่มต้นสำหรับแอปพลิเคชันคอนโซล #รวม "stdafx.h" #รวม ใช้เนมสเปซมาตรฐาน; float f(double x) // ส่งกลับค่าของฟังก์ชัน f(x) = x^2-2 float df(float x) // ส่งคืนค่าอนุพันธ์ float d2f(float x) // ค่าของอนุพันธ์อันดับสอง int _tmain (int argc, _TCHAR * argv) int exit = 0, i=0;//ตัวแปรสำหรับทางออกและลูป x0,xn;//การประมาณค่ารากที่คำนวณแล้ว double a, b, eps; // ขอบเขตของส่วนและความแม่นยำที่ต้องการ ศาล<<"Please input \n=>"; ซิน>>ก>>ข; // ป้อนขอบเขตของส่วนที่เราจะค้นหารูท ศาล<<"\nPlease input epsilon\n=>"; ซิน>>อีพีเอส; // ป้อนความแม่นยำในการคำนวณที่ต้องการ ถ้า (a > b) // ถ้าผู้ใช้ผสมขอบเขตของเซ็กเมนต์ ให้สลับมัน ถ้า (f(a)*f(b)>0) // ถ้าสัญญาณของฟังก์ชันที่ขอบของเซ็กเมนต์เหมือนกัน แสดงว่าไม่มีรูทที่นี่ ศาล<<"\nError! No roots in this interval\n"; ถ้า (f(a)*d2f(a)>0) x0 = a; // เพื่อเลือกจุดเริ่มต้น ให้ตรวจสอบ f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // พิจารณาการประมาณค่าแรก ศาล<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // จะคำนวณต่อไปจนกว่าเราจะได้ความแม่นยำที่ต้องการ xn = x0-f(x0)/df(x0); // สูตรของนิวตันโดยตรง ศาล<<++i<<"-th iteration = "< ศาล<<"\nRoot = "< ศาล<<"\nExit?=>"; ) ในขณะที่ (ออก!=1); // จนกว่าผู้ใช้จะเข้า exit = 1 |
มาดูกันว่ามันทำงานอย่างไร คลิกที่สามเหลี่ยมสีเขียวที่มุมซ้ายบนของหน้าจอ หรือกด F5
หากข้อผิดพลาดในการคอมไพล์เกิดขึ้น “ข้อผิดพลาดข้อผิดพลาด LNK1123: ไม่สามารถแปลงเป็น COFF: ไฟล์ไม่ถูกต้องหรือเสียหาย” สามารถแก้ไขได้โดยการติดตั้ง Service Pack 1 แรก หรือในคุณสมบัติการตั้งค่าโปรเจ็กต์ -> Linker ที่ปิดใช้งานการลิงก์ส่วนเพิ่ม
ข้าว. 4. การแก้ไขข้อผิดพลาดในการคอมไพล์โครงการ
เราจะค้นหารากของฟังก์ชัน ฉ(x) =x2-2.
ขั้นแรก เรามาตรวจสอบประสิทธิภาพของแอปพลิเคชันกับข้อมูลอินพุตที่ "ผิด" ไม่มีรากในส่วนนี้ โปรแกรมของเราควรแสดงข้อความแสดงข้อผิดพลาด
ตอนนี้เรามีหน้าต่างแอปพลิเคชัน:
ข้าว. 5. การป้อนข้อมูลเข้า
ให้เราแนะนำขอบเขตของส่วนที่ 3 และ 5 และความแม่นยำคือ 0.05 ตามที่คาดไว้ โปรแกรมสร้างข้อความแสดงข้อผิดพลาดว่าไม่มีรากในส่วนนี้
ข้าว. 6. ข้อผิดพลาด “ไม่มีรากในส่วนนี้!”
เรายังไม่ออกไปไหน แล้วข้อความ "ออก" ล่ะ ป้อน “0”
ตอนนี้เรามาตรวจสอบแอปพลิเคชันโดยใช้ข้อมูลอินพุตที่ถูกต้อง เข้าสู่ส่วนและความแม่นยำ 0.0001 กัน
ข้าว. 7. การคำนวณรูตด้วยความแม่นยำที่ต้องการ
ดังที่เราเห็นแล้วว่าได้รับความแม่นยำที่ต้องการแล้วในการวนซ้ำครั้งที่ 4
หากต้องการออกจากแอปพลิเคชัน ให้ป้อน “Exit?” => 1.
วิธีการตัด
เพื่อหลีกเลี่ยงการคำนวณอนุพันธ์ วิธีของนิวตันสามารถทำให้ง่ายขึ้นได้โดยการแทนที่อนุพันธ์ด้วยการประมาณที่คำนวณจากสองจุดก่อนหน้า:
กระบวนการทำซ้ำมีลักษณะดังนี้:
นี่เป็นกระบวนการวนซ้ำสองขั้นตอนเนื่องจากใช้สองขั้นตอนก่อนหน้าเพื่อค้นหาการประมาณถัดไป
ลำดับของการบรรจบกันของวิธีเซแคนต์นั้นต่ำกว่าลำดับของวิธีแทนเจนต์และเท่ากันในกรณีของรูทเดี่ยว
ปริมาณที่น่าทึ่งนี้เรียกว่าอัตราส่วนทองคำ:
ให้เราตรวจสอบสิ่งนี้โดยสมมุติเพื่อความสะดวกว่า
ดังนั้นจนถึงลำดับที่สูงกว่า
เมื่อละทิ้งเทอมที่เหลือ เราจะได้ความสัมพันธ์ที่เกิดซ้ำ ซึ่งเป็นวิธีแก้ปัญหาที่ค้นหาตามธรรมชาติในรูปแบบ
หลังจากการทดแทนเรามี: และ
เพื่อการบรรจบกัน จำเป็นต้องเป็นบวก ดังนั้น .
เนื่องจากไม่จำเป็นต้องมีความรู้เกี่ยวกับอนุพันธ์ ด้วยจำนวนการคำนวณที่เท่ากันในวิธีเซคแคนต์ (แม้จะมีลำดับการลู่เข้าที่ต่ำกว่า) เราจึงสามารถได้รับความแม่นยำมากกว่าในวิธีแทนเจนต์
โปรดทราบว่าใกล้กับรูทคุณต้องหารด้วยจำนวนเล็กน้อยซึ่งจะทำให้สูญเสียความแม่นยำ (โดยเฉพาะอย่างยิ่งในกรณีที่มีหลายรูท) ดังนั้นเมื่อเลือกจำนวนที่ค่อนข้างน้อยแล้วให้ทำการคำนวณก่อนดำเนินการ และทำต่อไปจนกว่าโมดูลัสของความแตกต่างระหว่างการประมาณใกล้เคียงจะลดลง
ทันทีที่การเติบโตเริ่มต้นขึ้น การคำนวณจะหยุดลงและจะไม่ใช้การวนซ้ำครั้งล่าสุด
ขั้นตอนในการกำหนดจุดสิ้นสุดของการวนซ้ำนี้เรียกว่าเทคนิค กาวิกา.
วิธีพาราโบลา
ลองพิจารณาวิธีการสามขั้นตอนซึ่งการประมาณจะถูกกำหนดโดยจุดสามจุดก่อนหน้า และ
ในการทำเช่นนี้ เราจะแทนที่ฟังก์ชันด้วยพาราโบลาการประมาณค่าที่ผ่านจุดต่างๆ ในทำนองเดียวกันกับวิธีตัดค่า และ
ในรูปของนิวตันดูเหมือนว่า:
จุดถูกกำหนดให้เป็นหนึ่งในรากของพหุนามนี้ที่มีค่าสัมบูรณ์ใกล้กับจุดมากกว่า
ลำดับการบรรจบกันของวิธีพาราโบลานั้นสูงกว่าลำดับการบรรจบกันของวิธีเซแคนต์ แต่ต่ำกว่าลำดับของวิธีของนิวตัน
ความแตกต่างที่สำคัญจากวิธีที่พิจารณาก่อนหน้านี้คือความจริงที่ว่า แม้ว่าจริงสำหรับจริงและการประมาณเริ่มต้นจะถูกเลือกให้เป็นจริง แต่วิธีพาราโบลาสามารถนำไปสู่รากที่ซับซ้อนของปัญหาดั้งเดิมได้
วิธีนี้สะดวกมากในการค้นหารากของพหุนามระดับสูง
วิธีการวนซ้ำอย่างง่าย
ปัญหาในการหาคำตอบของสมการสามารถกำหนดได้ว่าเป็นปัญหาในการหาราก: หรือเป็นปัญหาในการหาจุดคงที่
อนุญาต และ - การบีบอัด: (โดยเฉพาะอย่างยิ่งความจริงที่ว่า - การบีบอัด ดังที่เห็นได้ง่ายหมายความว่าเป็นเช่นนั้น)
ตามทฤษฎีบทของบานาค มีจุดคงที่เฉพาะจุดหนึ่ง
สามารถพบได้ว่าเป็นขีดจำกัดของกระบวนการวนซ้ำอย่างง่าย
โดยที่การประมาณเริ่มต้นเป็นจุดใดก็ได้ในช่วงเวลา
หากฟังก์ชันสามารถหาอนุพันธ์ได้ ตัวเลข จะเป็นเกณฑ์การบีบอัดที่สะดวก ตามทฤษฎีบทของลากรองจ์
ดังนั้นหากอนุพันธ์น้อยกว่า 1 แสดงว่ามันคือการบีบอัด
เงื่อนไข เป็นสิ่งจำเป็น เพราะถ้า ตัวอย่างเช่น บน แล้วไม่มีจุดคงที่ แม้ว่าอนุพันธ์จะเท่ากับศูนย์ก็ตาม ความเร็วของการบรรจบกันขึ้นอยู่กับค่าของ ยิ่งเล็ก ยิ่งการบรรจบกันเร็วขึ้น
ภาควิชาเคมีเชิงฟิสิกส์ SFU (RSU)
วิธีการเชิงตัวเลขและการเขียนโปรแกรม
วัสดุสำหรับหลักสูตรการบรรยาย
อาจารย์ – ศิลปะ สาธุคุณ ชเชอร์บาคอฟ ไอ.เอ็น.
ระบบสมการไม่เชิงเส้น
ในการแก้ปัญหาการสร้างแบบจำลองพฤติกรรมของระบบเคมี มักจำเป็นต้องแก้ระบบสมการที่ไม่เชิงเส้นเทียบกับตัวแปรต่างๆ ระบบ nสมการเชิงเส้นที่มี n ไม่ทราบ x 1, x 2, ..., xn โดยทั่วไปจะเขียนได้ดังนี้:
โดยที่ F 1, F 2,..., F n คือฟังก์ชันใดๆ ของตัวแปรอิสระ รวมถึงฟังก์ชันที่ไม่เชิงเส้นด้วยความเคารพต่อสิ่งที่ไม่ทราบ
เช่นเดียวกับในกรณีของระบบสมการเชิงเส้น ผลเฉลยของระบบคือเวกเตอร์ (หรือเวกเตอร์) (X *) ซึ่งเมื่อมีการทดแทน จะเปลี่ยนสมการทั้งหมดของระบบให้เป็นอัตลักษณ์ไปพร้อมๆ กัน
ระบบสมการอาจไม่มีคำตอบ มีเพียงคำตอบเดียว มีจำนวนคำตอบจำกัดหรือจำนวนอนันต์ คำถามเกี่ยวกับจำนวนวิธีแก้ไขจะต้องได้รับการแก้ไขสำหรับแต่ละปัญหาเฉพาะแยกกัน
ลองพิจารณาวิธีการวนซ้ำที่ง่ายที่สุดหลายวิธีในการแก้ระบบสมการไม่เชิงเส้น กล่าวคือ วิธีการวนซ้ำอย่างง่าย วิธีไซเดล และวิธีการนิวตัน
วิธีการวนซ้ำอย่างง่าย
การนำวิธีนี้ไปใช้จะต้องนำระบบสมการที่จะแก้มาเป็นรูปแบบต่อไปนี้โดยการแปลงพีชคณิต โดยแสดงตัวแปรหนึ่งตัวแปรจากแต่ละสมการดังนี้
จากนั้นเลือกเวกเตอร์การประมาณเริ่มต้น
แทนที่มันเข้าไปในระบบสมการที่แปลงแล้ว จากสมการแรก จะได้ค่าประมาณใหม่ไปจนถึงตัวแปรแรก จากสมการที่สอง - ที่สอง ฯลฯ ผลลัพธ์ที่ปรับแต่งแล้วของตัวแปรจะถูกแทนที่อีกครั้งในสมการเหล่านี้ เป็นต้น ดังนั้นที่ขั้นตอนที่ (i+1) ของกระบวนการวนซ้ำที่เรามี
วิธีไซเดล
การปรับเปลี่ยนอัลกอริธึมการวนซ้ำอย่างง่ายของ Seidel ประกอบด้วยการใช้ค่าที่ปรับปรุงแล้วของตัวแปรที่อยู่ในขั้นตอนการวนซ้ำปัจจุบัน ดังนั้นเพื่อชี้แจงค่าของตัวแปรแรกจะใช้เฉพาะค่าของขั้นตอนก่อนหน้าเท่านั้นสำหรับตัวแปรที่สอง - ค่า x 1 ของขั้นตอนปัจจุบันและส่วนที่เหลือ - จากตัวแปรก่อนหน้า ฯลฯ : :
วิธีนิวตัน-ราฟสัน
พื้นฐานทางคณิตศาสตร์ของวิธีนี้คือการทำให้ฟังก์ชันเชิงเส้นตรง เอฟ 1 , เอฟ 2 , ฟน (ทางด้านซ้ายของสมการที่กำลังสร้าง) โดยขยายเป็นอนุกรมเทย์เลอร์ในบริเวณใกล้กับจุดเริ่มต้นในการหาคำตอบ และละเลยเงื่อนไขทั้งหมดของอนุกรม ยกเว้นเชิงเส้นที่เกี่ยวข้องกับ เพิ่มขึ้นตัวแปร
ลองพิจารณาวิธีการโดยใช้ตัวอย่างระบบสมการสองสมการที่ไม่ทราบค่าสองตัว:
ลองทำให้ฟังก์ชันเป็นเชิงเส้นกัน เอฟ 1 , เอฟ 2 โดยขยายเป็นอนุกรม Taylor ใกล้จุดหนึ่ง (การประมาณเริ่มต้น) และละเลยเงื่อนไขทั้งหมดของอนุกรม ยกเว้นเชิงเส้นที่เกี่ยวข้องกับการเพิ่มตัวแปร
โปรดจำไว้ว่าสำหรับฟังก์ชันของตัวแปรตัวหนึ่ง การขยายตัวของอนุกรมเทย์เลอร์ในบริเวณใกล้จุด x 0 จะมีรูปแบบดังนี้:
หลังจากละเลยเงื่อนไขทั้งหมดยกเว้นเงื่อนไขเชิงเส้น:
สำหรับฟังก์ชันของตัวแปรหลายตัว การขยายจะดำเนินการในลักษณะเดียวกัน
หากต้องการหาคำตอบของระบบสมการ ให้เราเลือกการประมาณเบื้องต้น
มาเขียนฟังก์ชันกันดีกว่า เอฟ 1 ส่วนเชิงเส้น 2 ตัวแปรของการขยายซีรีส์ Taylor ในบริเวณใกล้เคียงกับจุดที่เลือก
สำหรับสมการที่สองในทำนองเดียวกัน
หากค่าของตัวแปร x 1 และ x 2 เป็นวิธีแก้ปัญหา ดังนั้นสมการทั้งสองของระบบจะต้องหายไป ดังนั้นเราจึงถือเอาการขยายผลลัพธ์ให้เป็นศูนย์
เพื่อความกระชับ เราขอแนะนำสัญลักษณ์ต่อไปนี้:
การเพิ่มขึ้นของตัวแปร i-th
ค่าของอนุพันธ์ย่อยตัวแรกของฟังก์ชัน เอฟ j โดยตัวแปร x i ที่ค่าของตัวแปร
– ค่าของฟังก์ชัน j -th ที่มีค่าที่สอดคล้องกันของตัวแปร นั่นคือความคลาดเคลื่อนของสมการ j -th
เราได้รับระบบสมการเชิงเส้น 2 x 2 เทียบกับการเพิ่มขึ้นของตัวแปร
หรือในรูปแบบเมทริกซ์
โดยที่เมทริกซ์ของค่าอนุพันธ์บางส่วนเรียกว่าเมทริกซ์จาโคบี (หรือ จาโคเบียน). คำตอบของระบบนี้ให้เวกเตอร์ของการแก้ไขการประมาณเริ่มต้น
การเพิ่มลงในเวกเตอร์การประมาณเริ่มต้นจะให้ค่าใหม่ของตัวแปร
ดังนั้นขั้นตอนการแก้ปัญหาจึงเป็นดังนี้:
1. เลือกการประมาณเริ่มต้น ระบบจะลดลงเป็นรูปแบบปกติ และอนุพันธ์ย่อยของด้านขวามือของสมการของระบบเทียบกับตัวแปรทั้งหมดจะพบในรูปแบบการวิเคราะห์
2. คำนวณเมทริกซ์จาโคเบียนของค่าอนุพันธ์บางส่วน ณ จุดประมาณเริ่มต้น
3. ระบบสมการเชิงเส้นได้รับการแก้ไขเพื่อเพิ่มตัวแปร
4. เวกเตอร์ส่วนเพิ่มจะถูกเพิ่มเข้าไปในเวกเตอร์การประมาณเริ่มต้น
5. มีการตรวจสอบเงื่อนไขการลู่เข้า และหากไม่บรรลุ ให้ทำซ้ำขั้นตอนจากขั้นตอนที่ 2
วิธีนี้สามารถสรุปได้ง่ายกับระบบสมการทุกมิติ
สำหรับฟังก์ชัน F 1 n
ตัวแปรเชิงเส้นส่วนหนึ่งของการขยายอนุกรม Taylor ในพื้นที่ใกล้เคียงของจุด เขียนแบบนี้
หลังจากแยกย่อยสมการทั้งหมดของระบบและใช้สัญกรณ์ที่แนะนำไว้ก่อนหน้านี้ หลังจากการแปลง เราจะได้ระบบสมการเชิงเส้นลำดับ n เทียบกับการเพิ่มขึ้นของตัวแปร Δ x i
หรือในรูปแบบเมทริกซ์
ในรูปแบบย่อเราสามารถเขียนได้เช่นนี้ - (F" )(Δ x ) = - (F ) โดยที่เมทริกซ์ของค่าอนุพันธ์บางส่วน - (F" ) - เรียกว่า เมทริกซ์จาโคเบียนหรือ จาโคเบียนระบบสมการ
คำตอบของระบบนี้ให้เวกเตอร์ของการแก้ไขการประมาณเริ่มต้น การเพิ่มลงในเวกเตอร์การประมาณเริ่มต้นจะให้ค่าใหม่ของตัวแปรที่ได้รับการปรับปรุง
อนุพันธ์บางส่วนที่จำเป็นสำหรับการคำนวณ เมทริกซ์จาโคเบียนสามารถคำนวณในเชิงวิเคราะห์ได้ หรือหากเป็นไปไม่ได้หรือยาก ได้รับโดยใช้สูตรการสร้างความแตกต่างโดยประมาณ เช่น เป็นอัตราส่วนของการเพิ่มขึ้นของฟังก์ชันต่อการเพิ่มขึ้นของอาร์กิวเมนต์
ที่ไหน เอปไซลอน– เป็นจำนวนที่ค่อนข้างน้อย
วิธีการควบคุมการบรรจบกันของวิธีการวนซ้ำ
โซลูชั่นระบบ
การบรรจบกันของกระบวนการวนซ้ำของการแก้ระบบสมการไม่เชิงเส้นสามารถควบคุมได้หลายวิธี เช่น
1. Norm (Euclidean หรือ -maximum) ของเวกเตอร์ตกค้าง
2. บรรทัดฐานแบบยุคลิดของเวกเตอร์ของการเบี่ยงเบนสัมพัทธ์ของตัวแปร
3. เวกเตอร์บรรทัดฐานสูงสุดของการเบี่ยงเบนสัมพัทธ์
ลองใช้วิธีของนิวตันในการแก้ระบบสมการกัน
เมทริกซ์อนุพันธ์บางส่วน (ในรูปแบบการวิเคราะห์)
ระบบสมการเชิงเส้น
สามารถแก้ไขได้ในเชิงวิเคราะห์หรือโดยวิธีแครมเมอร์หรือวิธีผกผันเมทริกซ์ ลองหาค่าประมาณเริ่มต้น x = 0.15, y = 0.17 กัน
การทำซ้ำครั้งแรก:
จาโคบีเมทริกซ์ - เวกเตอร์ของค่าฟังก์ชัน เวกเตอร์ที่คำนวณของการแก้ไข การประมาณใหม่ x = 0.15 + 0.028704 = 0.178704, y = 0.17 + 0.090926 = 0.260926 การทำซ้ำครั้งที่สอง:
เวกเตอร์การแก้ไขที่คำนวณได้ การประมาณใหม่ x = 0.196656, y = 0.293359 การทำซ้ำครั้งที่สาม:
เวกเตอร์การแก้ไขที่คำนวณแล้ว การประมาณใหม่ x = 0.199867, y = 0.299739 ในการวนซ้ำครั้งที่ 6 แล้ว บรรทัดฐานแบบยุคลิดของเวกเตอร์ที่เหลือคือ 2.8∙10 -13 การเปลี่ยนแปลงสัมพัทธ์สูงสุดของตัวแปรคือ 1.6∙10 -12 และผลเฉลยมาบรรจบกันที่ x = 0.2 , y = 0.3 โดยมีข้อผิดพลาดสัมบูรณ์น้อยกว่า 5∙10 -7 วิธีการวนซ้ำอย่างง่ายภายใต้เงื่อนไขเริ่มต้นเดียวกันจะมาบรรจบกันด้วยความแม่นยำเท่ากันในขั้นตอนที่ 33 การดัดแปลง Seidel - ในขั้นตอนที่ 31 รูปด้านล่างแสดงตัวอย่างการจัดองค์กรการคำนวณเมื่อแก้ไขระบบที่พิจารณาใน MS Excel
คำอธิบาย:เซลล์ B3 และ B4 มีการประมาณเริ่มต้นของการแก้ปัญหาของระบบ (ค่า x 0 และ y 0 ตามลำดับ) ในช่วงของเซลล์ D3:E4 มีสูตรสำหรับคำนวณเมทริกซ์จาโคเบียน โดยมีเงื่อนไขว่า x อยู่ในเซลล์ B3 และ y อยู่ในเซลล์ B4 (สูตรแสดงในรูปด้านล่าง) ในเซลล์ G3:G4 จะมีการคำนวณค่าของเวกเตอร์ของสารตกค้างที่มีเครื่องหมายลบ
ในเซลล์ H3 จะมีการคำนวณบรรทัดฐานแบบยุคลิดของเวกเตอร์ที่เหลือ ในเซลล์ I3:I4 ระบบสมการเชิงเส้นได้รับการแก้ไขแล้ว และเวกเตอร์ของการแก้ไขสารละลายจะถูกคำนวณ เมื่อต้องการทำเช่นนี้ เมทริกซ์ของค่าสัมประสิทธิ์ระบบ (เมทริกซ์จาโคบี) จะถูกกลับด้านและคูณด้วยเวกเตอร์คอลัมน์ของเทอมอิสระ (เวกเตอร์เชิงลบของส่วนที่เหลือ) สูตรในช่วงของเซลล์นี้จะถูกป้อนเป็นสูตรอาร์เรย์ ใกล้เคียง - ในเซลล์ J3 - บรรทัดฐานของเวกเตอร์การแก้ไขถูกคำนวณเพื่อควบคุมการลู่เข้า (ดูสูตรในรูปด้านล่าง)
ค่าแก้ไขที่ได้รับในเซลล์ I3:I4 ในรอบการวนซ้ำครั้งที่สองจะถูกเพิ่มลงในการประมาณเริ่มต้น (ในเซลล์ B6:B7) จากนั้นการคำนวณจะทำซ้ำในทำนองเดียวกันกับรอบแรก สามารถคัดลอกสูตรที่พิมพ์ในบรรทัดที่ 6 และ 7 ของแผ่นงานได้จนกว่าจะได้ความแม่นยำที่ต้องการ
ปัญหาที่ลดลงไปสู่การแก้ระบบสมการไม่เชิงเส้น
ตัวอย่างของปัญหาที่ใช้วิธีแก้ระบบสมการไม่เชิงเส้นคือการประมาณฟังก์ชันที่ระบุในตารางโดยใช้แบบจำลองทางคณิตศาสตร์ที่ไม่เชิงเส้นเทียบกับพารามิเตอร์ ได้มีการอธิบายไว้โดยละเอียดแล้วก่อนหน้านี้ หากฟังก์ชันการประมาณและพารามิเตอร์การกำหนด ฉัน กำหนดดังต่อไปนี้ จากนั้นเงื่อนไขในการผ่านกราฟฟังก์ชันผ่านจุดตารางทั้งหมดสามารถเขียนได้ในรูปของระบบดังต่อไปนี้ อีกตัวอย่างหนึ่งคือการค้นหาฟังก์ชันสุดขีด (ต่ำสุดหรือสูงสุด) ของฟังก์ชันของตัวแปรหลายตัว เงื่อนไขของค่าสุดขีดคือความเท่ากันกับศูนย์ของอนุพันธ์ย่อยทั้งหมดของฟังก์ชันพร้อมกัน จึงต้องแก้ระบบสมการตามรูปแบบต่อไปนี้ ซึ่งในกรณีทั่วไปจะเป็นแบบไม่เชิงเส้น
วิธีการวนซ้ำอย่างง่าย หรือที่เรียกว่าวิธีการประมาณต่อเนื่อง เป็นอัลกอริทึมทางคณิตศาสตร์สำหรับการค้นหาค่าของปริมาณที่ไม่ทราบโดยการค่อยๆ ทำให้บริสุทธิ์ สาระสำคัญของวิธีการนี้คือตามชื่อที่แนะนำโดยค่อยๆ แสดงผลที่ตามมาจากการประมาณเริ่มต้น จะได้ผลลัพธ์ที่ละเอียดมากขึ้นเรื่อยๆ วิธีการนี้ใช้เพื่อค้นหาค่าของตัวแปรในฟังก์ชันที่กำหนด ตลอดจนใช้ในการแก้ระบบสมการทั้งเชิงเส้นและไม่เชิงเส้น
ให้เราพิจารณาว่าวิธีการนี้ถูกนำมาใช้อย่างไรเมื่อแก้ไข SLAE วิธีการวนซ้ำอย่างง่ายมีอัลกอริทึมดังต่อไปนี้:
1. การตรวจสอบการปฏิบัติตามเงื่อนไขการลู่เข้าในเมทริกซ์ดั้งเดิม ทฤษฎีบทการลู่เข้า: หากเมทริกซ์ดั้งเดิมของระบบมีความโดดเด่นในแนวทแยง (นั่นคือ ในแต่ละแถว องค์ประกอบของเส้นทแยงมุมหลักต้องมีค่าสัมบูรณ์มากกว่าผลรวมขององค์ประกอบของเส้นทแยงมุมรองด้วยค่าสัมบูรณ์) ดังนั้นค่าสัมบูรณ์แบบง่าย วิธีการวนซ้ำเป็นแบบมาบรรจบกัน
2. เมทริกซ์ของระบบดั้งเดิมไม่ได้มีความโดดเด่นในแนวทแยงเสมอไป ในกรณีเช่นนี้สามารถแปลงระบบได้ สมการที่ตรงตามเงื่อนไขการลู่เข้าจะไม่ถูกแตะต้อง และสมการเชิงเส้นจะถูกสร้างขึ้นด้วยสมการที่ไม่เข้ากัน เช่น คูณ ลบ บวกสมการกันจนได้ผลลัพธ์ที่ต้องการ
หากในระบบผลลัพธ์มีค่าสัมประสิทธิ์ที่ไม่สะดวกบนเส้นทแยงมุมหลักเงื่อนไขของแบบฟอร์มที่มี i * x i จะถูกเพิ่มลงทั้งสองด้านของสมการซึ่งสัญญาณจะต้องตรงกับสัญญาณขององค์ประกอบในแนวทแยง
3. การเปลี่ยนแปลงของระบบผลลัพธ์ให้เป็นรูปแบบปกติ:
x - =β - +α*x -
สิ่งนี้สามารถทำได้หลายวิธีเช่น: จากสมการแรกแสดง x 1 ในรูปของไม่ทราบอื่น ๆ จากที่สอง - x 2 จากที่สาม - x 3 เป็นต้น ในกรณีนี้เราใช้สูตร:
α ij = -(a ij / a ii)
ฉัน = ข ฉัน /a ii
คุณควรตรวจสอบให้แน่ใจอีกครั้งว่าระบบผลลัพธ์ของรูปแบบปกติตรงตามเงื่อนไขการลู่เข้า:
∑ (j=1) |α ij |≤ 1 ในขณะที่ i= 1,2,...n
4. อันที่จริงเราเริ่มใช้วิธีการประมาณต่อเนื่องกัน
x (0) คือการประมาณค่าเริ่มต้น เราจะเขียน x (1) ผ่านค่านั้น จากนั้นเราจะเขียนค่า x (2) ถึง x (1) สูตรทั่วไปในรูปแบบเมทริกซ์มีลักษณะดังนี้:
x (n) = β - +α*x (n-1)
เราคำนวณจนกว่าเราจะบรรลุความแม่นยำที่ต้องการ:
สูงสุด | x i (k)-x i (k+1) ≤ ε
ดังนั้น เรามานำวิธีการวนซ้ำแบบง่ายๆ มาปฏิบัติกัน ตัวอย่าง:
แก้ SLAE:
4.5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 ด้วยความแม่นยำ ε=10 -3
มาดูกันว่าองค์ประกอบในแนวทแยงมีอิทธิพลเหนือโมดูลัสหรือไม่
เราจะเห็นว่ามีเพียงสมการที่สามเท่านั้นที่ตรงตามเงื่อนไขการลู่เข้า มาแปลงสมการที่หนึ่งและที่สองกัน แล้วบวกอันที่สองเข้ากับสมการแรก:
7.6x1+0.6x2+2.4x3=3
จากอันที่สามเราลบอันแรก:
2.7x1+4.2x2+1.2x3=2
เราแปลงระบบดั้งเดิมเป็นระบบที่เทียบเท่า:
7.6x1+0.6x2+2.4x3=3
-2.7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4
ตอนนี้เรามาทำให้ระบบกลับสู่รูปแบบปกติ:
x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3= 0.8511-0.383x1-0.5319x2
เราตรวจสอบการบรรจบกันของกระบวนการวนซ้ำ:
0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383+ 0.5319= 0.9149 ≤ 1 เช่น ตรงตามเงื่อนไข
0,3947
การเดาเริ่มต้น x(0) = 0.4762
0,8511
เมื่อแทนค่าเหล่านี้ลงในสมการของรูปแบบปกติเราจะได้ค่าต่อไปนี้:
0,08835
x(1) = 0.486793
0,446639
แทนที่ค่าใหม่เราจะได้:
0,215243
x(2) = 0.405396
0,558336
เราทำการคำนวณต่อไปจนกว่าเราจะเข้าใกล้ค่าที่ตรงตามเงื่อนไขที่กำหนด
x (7) = 0.441091
ตรวจสอบความถูกต้องของผลลัพธ์ที่ได้รับ:
4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0.1880+2.3*0.441-1.1x*0.544=0.9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977
ผลลัพธ์ที่ได้จากการแทนที่ค่าที่พบลงในสมการดั้งเดิมนั้นตรงตามเงื่อนไขของสมการโดยสมบูรณ์
ดังที่เราเห็น วิธีการวนซ้ำอย่างง่ายให้ผลลัพธ์ที่ค่อนข้างแม่นยำ แต่ในการแก้สมการนี้ เราต้องใช้เวลามากและทำการคำนวณที่ยุ่งยาก