Шугаман бус тэгшитгэлийн онол ба хуваах арга. Дихотомийн арга буюу хуваах арга
Хагас хуваах арга(бусад нэрс: хуваах арга, дихотомийн арга) тэгшитгэлийг шийдвэрлэх е(x) = 0 нь дараах байдалтай байна. Функц нь тасралтгүй бөгөөд сегментийн төгсгөлийг авдаг гэдгийг мэдэгдье
[а, б] өөр өөр тэмдгийн утгууд, дараа нь үндэс нь интервалд агуулагдана ( а, б). Интервалыг хоёр хагас болгон хувааж, төгсгөлд нь функц өөр өөр тэмдгийн утгыг авах талыг авч үзье. Бид энэ шинэ сегментийг дахин хоёр тэнцүү хэсэгт хувааж, үндэс агуулсан хэсгийг сонгоно. Дараагийн сегментийн урт нь шаардлагатай алдааны утгаас бага болтол энэ процесс үргэлжилнэ. Бисекцийн аргын алгоритмын илүү нарийн танилцуулга:
1) Тооцоолъё x = (а+ б)/2; тооцоолъё е(x);
2) Хэрэв е(x) = 0, дараа нь 5-р алхам руу очно уу;
3) Хэрэв е(x)∙е(а) < 0, то б = x, өөрөөр а = x;
4) Хэрэв | б – а| > ε, 1-р цэг рүү очно уу;
5) утгыг гарга x;
Жишээ 2.4.Бисекцийн аргыг ашиглан тэгшитгэлийн үндсийг боловсронгуй болгох ( x– 1) 3 = 0, сегментэд хамаарах .
Програм дахь шийдэл Excel:
1) эсүүдэд А 1:Ф 4 Бид Хүснэгт 2.3-т үзүүлсэн шиг тэмдэглэгээ, анхны утга, томъёог танилцуулж байна.
2) Томъёо бүрийг арав дахь мөр хүртэл дүүргэх тэмдэглэгээгээр доод нүднүүдэд хуулна. Б 4 - хүртэл Б 10, C 4 - хүртэл C 10, Д 3 - хүртэл Д 10, Э 4 - хүртэл Э 10, Ф 3 - хүртэл Ф 10.
Хүснэгт 2.3
| А | Б | C | Д | Э | Ф | |
| f(a)= | =(1-B3)^3 | |||||
| к | а | x | f(x) | б | б-а | |
| 0,95 | =(B3+E3)/2 | =(1-C3)^3 | 1,1 | =E3-B3 | ||
| =Хэрэв(D3=0,C3; IF(C$1*D3<0;B3;C3)) | =Хэрэв(C$1*D3>0; E3;C3) |
Тооцооллын үр дүнг хүснэгтэд үзүүлэв. 2.4. Баганад Финтервалын уртын утгыг шалгах б – а. Хэрэв утга нь 0.01-ээс бага бол энэ мөрөнд заасан алдаатай язгуурын ойролцоо утгыг олно. Шаардлагатай нарийвчлалд хүрэхийн тулд 5 удаа давталт хийсэн. Гурван бутархай руу бөөрөнхийлсний дараа 0.01 нарийвчлалтай язгуурын ойролцоо утга нь 1.0015625 ≈ 1.00 байна.
Хүснэгт 2.4
| А | Б | C | Д | Э | Ф | |
| f(a)= | 0,000125 | |||||
| к | а | x | f(x) | б | б-а | |
| 0,95 | 1,025 | -2E-05 | 1,1 | 0,15 | ||
| 0,95 | 0,9875 | 2E-06 | 1,025 | 0,075 | ||
| 0,9875 | 1,00625 | -2E-07 | 1,025 | 0,0375 | ||
| 0,9875 | 0,996875 | 3.1E-08 | 1,00625 | 0,0187 | ||
| 0,996875 | 1,0015625 | -4E-09 | 1,00625 | 0,0094 | ||
| 0,996875 | 0,9992188 | 4.8E-10 | 1,0015625 | 0,0047 | ||
| 0,99921875 | 1,0003906 | -6E-11 | 1,0015625 | 0,0023 | ||
| 0,99921875 | 0,9998047 | 7.5E-12 | 1,000390625 | 0,0012 |
Өгөгдсөн алгоритм нь харгалзан үздэг боломжтой тохиолдол"үндсээр нь цохих", өөрөөр хэлбэл. тэгш байдал е(x) дараагийн шатанд тэг. Хэрэв жишээ 2.3 дээр бид сегментийг авбал эхний алхамд бид үндэс рүү очно x= 1. Үнэхээр нүдэндээ бичье Б 3 утга 0.9. Дараа нь үр дүнгийн хүснэгт 2.5 хэлбэрийг авна (зөвхөн 2 давталт өгсөн).
Хүснэгт 2.5
| А | Б | C | Д | Э | Ф | |
| f(a)= | 0,001 | |||||
| к | а | x | f(x) | б | б-а | |
| 0,9 | 1,1 | 0,2 | ||||
Үүнийг программ дээр бүтээцгээе ExcelСуурилуулсан хэлийг ашиглан бисект аргыг ашиглан тэгшитгэлийг шийдвэрлэх f(x) ба bisect(a, b, eps) функцууд Visual Basic. Тэдний тайлбарыг доор өгөв.
Функц f(Бивал x)
Хоёр хэсэг функц (a, b, eps)
1 x = (a + b) / 2
Хэрэв f(x) = 0 бол 5 руу яв
Хэрэв f(x) * f(a) бол< 0 Then
Хэрэв Abs(a - b) > eps бол 1 рүү яв
f(x) функц тодорхойлно зүүн талтэгшитгэл ба функц
bisect(a, b, eps) нь bisect аргыг ашиглан тэгшитгэлийн язгуурыг тооцоолно е(x) = 0. bisect(a, b, eps) функц нь f(x) функцэд хандах хандалтыг ашигладаг болохыг анхаарна уу. Захиалгат функцийг бий болгох алгоритм энд байна:
1) "Хэрэгслүүд - Макро - Редактор" цэсийн командыг гүйцэтгэнэ Visual Basic" Цонх " Microsoft Visual Basic" Хэрэв энэ програмын файлд байгаа бол Excelмакро эсвэл хэрэглэгчийн функц, процедур хараахан үүсгэгдээгүй байгаа бол энэ цонх нь 2.4-р зурагт үзүүлсэн шиг харагдах болно.
2) "Insert - Module" цэсний командыг ажиллуулж, 2.5-р зурагт үзүүлсэн шиг програмын функцуудын текстийг оруулна.
Одоо програмын хуудасны нүднүүдэд ExcelТа үүсгэсэн функцуудыг томъёонд ашиглаж болно. Жишээлбэл, нүд рүү орцгооё Д 18 томъёо
Бисект(0.95;1;0.00001),
тэгвэл бид 0.999993896 утгыг авна.
Өөр тэгшитгэлийг (өөр зүүн талтай) шийдэхийн тулд та "Хэрэгслүүд - Макро - Редактор" командыг ашиглан засварлагч цонх руу очих хэрэгтэй. Visual Basic” гэж бичээд f(x) функцийн тайлбарыг дахин бичнэ. Жишээлбэл, sin5 тэгшитгэлийн язгуурыг 0.001 нарийвчлалтайгаар олъё. x + x 2 – 1 = 0, интервалд хамаарах (0.4; 0.5). Үүнийг хийхийн тулд функцийн тайлбарыг өөрчилье
шинэ тайлбарын хувьд
f = Нүгэл (5 * x) + x^2 - 1
Дараа нь үүрэнд Д 18 бид 0.441009521 утгыг авна (энэ үр дүнг 2.3-р жишээнд олдсон интервалын язгуурын (0.4; 0.5) утгатай харьцуулна уу!).
Програмд хагас хуваах аргыг ашиглан тэгшитгэлийг шийдэх Mathcadдэд программын функц үүсгэцгээе бисек(е, а, б, ε), энд:
f-тэгшитгэлийн зүүн талд тохирох функцийн нэр е(x) = 0;
а, б- сегментийн зүүн ба баруун төгсгөлүүд [ а, б];
ε - язгуурын ойролцоо утгын нарийвчлал.
Програм дээрх жишээний шийдэл Mathcad:
1) Програмыг ажиллуулна уу Mathcad.Функцийн тодорхойлолтыг танилцуулъя бисек(е, а, б, ε). Үүнийг хийхийн тулд гар болон "Грекийн тэмдгүүд" хэрэгслийн самбарыг ашиглан бичнэ үү бисек(е, а, б, ε):=. “Програмчлалын” хэрэгслийн самбар дээрх “:=” даалгаврын тэмдгийн дараа хулганы заагчийг ашиглан “Мөр нэмэх” дээр зүүн товшино уу. Даалгаврын тэмдгийн дараа босоо шугам гарч ирнэ. Дараа нь доор үзүүлсэн програмын текстийг "Програмчлалын" хэрэгслийн мөрийг ашиглан "←" тэмдгийг оруулахын тулд давталтын операторыг оруулна уу. байхад, оператор завсарлагаболон нөхцөлт оператор хэрэв өөрөөр бол.
2) Функцийн тодорхойлолтыг танилцуулъя е(x):=sin(5*x)+x^2–1, дараа нь функцийг ашиглан язгуурын утгыг тооцоол бисекөгөгдсөн утгууд дээр:
бисек(е, –0.8,–0.7,0.0001)=. “=” тэмдгийн дараа –0.7266601563 програмаар тооцсон үндсэн утга автоматаар гарч ирнэ. Үлдсэн үндсийг ижил аргаар тооцоолъё.
Доорх хуудас байна Mathcadфункцийн тодорхойлолттой бисек(е, а, б, ε) ба тооцоолол:
Хэл дээр нь нэвтрүүлэг өгье Cтэгшитгэлийг шийдэхийн тулд ++ е(x) = 0 хагас хуваах аргаар:
#оруулна
#оруулна
давхар f(давхар х);
typedef давхар (*PF)(давхар);
давхар биссек(PF f, давхар a, давхар b, давхар eps);
давхар a, b, x, eps;PF pf;
cout<< "\n a = "; cin >>a;
cout<< "\n b = "; cin >>b;
cout<< "\n eps = "; cin >> eps;
x = bisec(pf,a,b,eps); cout<< "\n x = " << x;
cout<< "\n Press any key & Enter "; cin >>a;
давхар f(давхар х)(
r = нүгэл(5*х)+х*х-1;
давхар биссек(PF f, double a, double b,double eps)(
хийх( x = (a + b)/2;
хэрэв (f(x) == 0) тасарвал;
хэрэв (f(x)*f(a)<0) b = x;
)while (fabs(b-a) > eps);
Програм дахь функц е(x) тэгшитгэлийг шийдэхийн тулд тодорхойлогддог
гэм 5 x + x 2 – 1 = 0
жишээ 2.3-аас. 0.00001 нарийвчлалтай интервалын үндсийг (0.4; 0.5) тодорхойлох програмын үр дүнг доор үзүүлэв (компьютерийн дэлгэц):
Дурын товчийг дараад Enter хийнэ үү
Сүүлийн мөр нь үр дүнг харахын тулд түр зогсолтыг зохион байгуулахад шаардлагатай.
Шугаман бус тэгшитгэлийг алгебрийн ба трансцендентал гэсэн 2 ангилалд хувааж болно. Алгебрийн тэгшитгэлзөвхөн алгебрийн функцуудыг (бүхэл тоо, рациональ, иррациональ) агуулсан тэгшитгэл гэж нэрлэдэг. Ялангуяа олон гишүүнт нь бүхэл бүтэн алгебрийн функц юм. Бусад функцуудыг (тригонометр, экспоненциал, логарифм гэх мэт) агуулсан тэгшитгэлийг нэрлэдэг. трансцендентал.
Шугаман бус тэгшитгэлийг шийдвэрлэх аргуудыг хоёр бүлэгт хуваадаг.
- нарийн аргууд ;
- давтагдах аргууд .
Яг тодорхой аргууд нь үндсийг зарим хязгаарлагдмал хамаарал (томъёо) хэлбэрээр бичих боломжийг олгодог. Сургуулийн алгебрийн хичээлээс ийм аргыг тригонометр, логарифм, экспоненциал, түүнчлэн энгийн алгебрийн тэгшитгэлийг шийдвэрлэхэд мэддэг.
Мэдэгдэж байгаагаар олон тэгшитгэл, тэгшитгэлийн системд аналитик шийдэл байдаггүй. Энэ нь үндсэндээ ихэнх трансцендент тэгшитгэлд хамаатай. Мөн дөрвөөс дээш градусын дурын алгебрийн тэгшитгэлийг шийдэх томьёог бүтээх боломжгүй гэдэг нь батлагдсан. Нэмж дурдахад зарим тохиолдолд тэгшитгэл нь зөвхөн ойролцоогоор мэдэгдэж байгаа коэффициентүүдийг агуулдаг тул тэгшитгэлийн үндсийг үнэн зөв тодорхойлох үүрэг нь утгаа алддаг. Тэдгээрийг шийдэхийн тулд бид ашигладаг давтагдах аргуудөгөгдсөн нарийвчлалын зэрэгтэй.
Тэгшитгэлийг өгье
- Чиг үүрэг е(x) [ интервал дээр тасралтгүй байна а, б] 1 ба 2-р эрэмбийн деривативын хамт.
- Үнэ цэнэ е(x) сегментийн төгсгөлд өөр өөр тэмдэгтэй байна ( е(а) * е(б) < 0).
- Эхний болон хоёр дахь деривативууд f"(x) Мөн f""(x) бүх сегментийн туршид тодорхой тэмдгийг хадгална.
Нөхцөл 1) ба 2) нь [ интервал дээр байх баталгаа юм. а, б] дор хаяж нэг язгуур байдаг ба 3)-аас үүнийг дагадаг е(x) нь энэ интервал дээр монотон байх тул үндэс нь өвөрмөц байх болно.
Тэгшитгэлийг шийдэх (1) давталтын аргаЭнэ нь үндэстэй эсэх, хэдэн үндэстэй болохыг тогтоож, язгуурын утгыг шаардлагатай нарийвчлалтайгаар олох гэсэн үг юм.
Функцийг буцаах аливаа утга е(x) тэг хүртэл, өөрөөр хэлбэл. ийм байдлаар:
дуудсан үндэс тэгшитгэл(1) эсвэл тэгфункцууд е(x).
Тэгшитгэлийн язгуурыг олох асуудал е(xДавталтын аргаар ) = 0 нь хоёр үе шатаас бүрдэнэ.
- үндэс тусгаарлалт - үндэс эсвэл түүнийг агуулсан сегментийн ойролцоо утгыг олох;
- ойролцоогоор үндсийг боловсронгуй болгох - тэдгээрийг тодорхой нарийвчлалын түвшинд хүргэх.
Үндэс салгах үйл явц нь функцийн шинж тэмдгийг тогтоохоос эхэлдэг е(x) хил дээр x=аТэгээд x=боршин буй бүс нутгийн цэгүүд.
Жишээ 1 . Тэгшитгэлийн язгуурыг салга:
|
f( x) є x 3 - 6x + 2 = 0. |
Ойролцоогоор диаграммыг хийцгээе:
Иймээс (2) тэгшитгэл нь [-3, -1], ба завсарт орших гурван бодит язгууртай байна.
Үндэсний ойролцоо утгууд ( Анхны ойролцоо тооцоолол) нь асуудлын физик утгаас, өөр өөр анхны өгөгдөлтэй ижил төстэй асуудлыг шийдвэрлэхээс мэдэж болно, эсвэл графикаар олж болно.
Инженерийн практикт түгээмэл байдаг график аргаойролцоо үндсийг тодорхойлох.
(1) тэгшитгэлийн бодит язгуурууд нь функцийн графикийн огтлолцох цэгүүд гэдгийг харгалзан үзвэл е(x) x тэнхлэгтэй бол функцийг зурахад хангалттай е(x) болон огтлолцох цэгүүдийг тэмдэглэнэ е(x) тэнхлэгтэй Өө,эсвэл тэнхлэг дээр тэмдэг тавина Өөнэг үндэс агуулсан сегментүүд. График барих ажлыг ихэвчлэн (1) тэгшитгэлийг орлуулах замаар ихээхэн хялбарчилж болно. тэнцүүтүүнийг тэгшитгэлээр:
Тэгшитгэл (4)-ийг тэгшитгэл болгон хялбархан дахин бичиж болно.
Эндээс (4) тэгшитгэлийн язгуурыг логарифмын муруйн огтлолцох цэгүүдийн абсцисса хэлбэрээр олж болох нь тодорхой байна. y= бүртгэл xба гипербол y = . Эдгээр муруйг байгуулсны дараа бид (4) тэгшитгэлийн цорын ганц язгуурыг олох эсвэл түүнийг агуулсан сегментийг тодорхойлох болно.
Давтагдах үйл явц нь анхны ойролцооллыг дараалан боловсронгуй болгохоос бүрдэнэ X 0 . Ийм алхам бүрийг нэрлэдэг давталт. Давталтын үр дүнд ойролцоогоор үндсэн утгуудын дараалал олддог X 1 , X 2 , ..., xn.Хэрэв эдгээр утгууд давталтын тоо нэмэгдэх тусам nязгуурын жинхэнэ утгад ойртож, дараа нь бид давтагдах үйл явц гэж хэлдэг нийлдэг.
[ сегментэд хамаарах (1) тэгшитгэлийн язгуурыг олохын тулд а, б], энэ сегментийг хагасаар хуваа. Хэрэв е= 0, дараа нь x = тэгшитгэлийн үндэс юм. Хэрэв е 0-тэй тэнцүү биш (энэ нь бодит байдал дээр хамгийн их магадлалтай), бид хагасын аль нэгийг эсвэл төгсгөлд нь функцийг сонгоно. е(x) эсрэг шинж тэмдэгтэй. Шинэ нарийссан сегмент [ А 1 , б 1] дахин хагаст хувааж, ижил үйлдлийг гүйцэтгэнэ.
Хагаслах арга нь өгөгдсөн тэгшитгэлийн үндсийг олоход бараг тохиромжтой бөгөөд энэ арга нь энгийн бөгөөд найдвартай бөгөөд үргэлж нэгддэг.
Жишээ 3. Тэгшитгэлийн язгуурыг тодруулахын тулд хагас хуваах аргыг ашигла
f( x) = x 4 + 2 x 3 - x - 1 = 0
[0, 1] сегмент дээр хэвтэж байна.
Бидэнд тогтмол байдаг:
f(0) = - 1; е(1) = 1; е(0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;
f(0.75) = 0.32 + 0.84 - 0.75 - 1 = - 0.59;
f(0.875) = 0.59 + 1.34 - 0.88 - 1 = + 0.05;
f(0.8125) = 0.436 + 1.072 - 0.812 - 1 = - 0.304;
f(0.8438) = 0.507 + 1.202 - 0.844 - 1 = - 0.135;
f(0.8594) = 0.546 + 1.270 - 0.859 - 1 = - 0.043 гэх мэт.
Хүлээн зөвшөөрч болно
x = (0.859 + 0.875) = 0.867
Энэ аргын хувьд давталтын үйл явц нь тэгшитгэлийн язгуурт (1) ойртсон дараах утгуудаас бүрдэнэ. X 1 , X 2 , ..., x nхөвчний огтлолцлын цэгүүд AB x тэнхлэгтэй (Зураг 3). Эхлээд бид хөвчний тэгшитгэлийг бичнэ AB:
.
Хөвчний огтлолцлын цэгийн хувьд AB x тэнхлэгтэй ( x = x 1 ,у= 0) бид тэгшитгэлийг авна:
Баттай байя f""(x) > 0 цагт a x b(болж байна f""(x) < Хэрэв бид тэгшитгэлийг хэлбэрээр бичвэл 0 нь буурна. е(x) = 0). Дараа нь муруй цагт = е(x) нь доошоо гүдгэр байх ба тиймээс түүний хөвчний доор байрлана AB. Хоёр боломжит тохиолдол байдаг: 1) е(А) > 0 (Зураг 3, А) ба 2) е(б) < 0 (Рисунок 3, б).
Зураг 3, a, b.
Эхний тохиолдолд төгсгөл Ахөдөлгөөнгүй ба дараалсан ойролцоо тоо: x 0 = б;x , энд функц байна е (X) хоёр дахь деривативын тэмдгийн эсрэг тэмдэгтэй байна f""(X).
Үүнийг олох хүртэл давтагдах үйл явц үргэлжилнэ
| x i - x i - 1 |< e ,
Энд e нь заасан хамгийн их үнэмлэхүй алдаа юм.
Жишээ 4. Тэгшитгэлийн эерэг язгуурыг ол
f( x) = x 3 - 0,2 x 2 - 0,2 X - 1,2 = 0
e = 0.01 нарийвчлалтай.
Юуны өмнө бид үндсийг нь салгадаг. Учир нь
f(1) = -0.6< 0 и е (2) = 5,6 > 0,
тэгвэл шаардлагатай язгуур х нь интервалд оршдог. Үр дүнгийн интервал нь том тул бид үүнийг хагасаар хуваана. Учир нь
f (1.5) = 1.425 > 0, дараа нь 1< x < 1,5.
Учир нь f""(x) = 6 x- 1-д 0.4 > 0< X < 1,5 и е(1.5) > 0, дараа нь бид асуудлыг шийдэхийн тулд (5) томъёог ашиглана:
= 1,15;
| x 1-х 0 | = 0.15 > e,
Тиймээс бид тооцооллыг үргэлжлүүлж байна;
f ( X 1) = -0,173;
= 1,190;
|x 2-х 1 | = 0.04 > e,
е (X 2) = -0,036;
= 1,198;
| x 3-х 2 | = 0,008 < e .
Тиймээс бид x = 1.198-ийг e = 0.01 нарийвчлалтайгаар авч болно.
Тэгшитгэлийн яг язгуур нь x = 1.2 гэдгийг анхаарна уу.
Дихотоми аргаЭнэ нэр нь эртний Грек үгнээс гаралтай бөгөөд орчуулбал хоёр хуваагдах гэсэн утгатай. Тийм ч учраас энэ арга нь хоёр дахь нэртэй байдаг: хагас бууруулах арга. Бид үүнийг нэлээд олон удаа ашигладаг. Нэг тоглогч 1-ээс 100 хүртэлх тоог тааж, нөгөө нь "илүү" эсвэл "бага" гэсэн сэжүүрээр удирдан таах гэж оролддог "Тоог таах" тоглоом тоглолоо гэж бодъё. Эхний тоог 50, бага бол хоёр дахь тоог 25, илүү бол 75 гэж нэрлэх нь логик юм. Тиймээс үе шат бүрт (давталт) үл мэдэгдэх байдлын тодорхойгүй байдал 2 дахин багасдаг. Тэдгээр. Дэлхийн хамгийн азгүй хүн ч гэсэн энэ муж дахь нуугдмал тоог 100 санамсаргүй мэдэгдлийн оронд 7 таамаглалаар таах болно.
Тэгшитгэлийг шийдвэрлэхэд хагас хуваах арга
Өгөгдсөн интервал дээр язгуур байдаг бөгөөд энэ нь цорын ганц гэдгийг мэддэг тохиолдолд л хагасын аргыг ашиглан тэгшитгэлийг зөв шийдэх боломжтой. Энэ нь дихотомийн аргыг зөвхөн шугаман тэгшитгэлийг шийдвэрлэхэд ашиглаж болно гэсэн үг биш юм. Дээд эрэмбийн тэгшитгэлийн үндсийг хуваах аргыг ашиглан олохын тулд эхлээд үндсийг сегмент болгон салгах хэрэгтэй. Үндэсийг салгах үйл явц нь функцийн нэг ба хоёрдугаар деривативыг олж, тэг f"(x)=0 ба f""(x)=0-тэй тэнцүүлэх замаар явагдана. Дараа нь f(x)-ийн тэмдгүүд. эгзэгтэй ба хилийн цэгүүдэд функцийн тэмдэг өөрчлөгдөх интервал тодорхойлогдоно, энд f(a)*f(b).< 0.
Дихотоми аргын алгоритм
Дихотоми аргын алгоритм нь маш энгийн. |a,b| сегментийг авч үзье дотор нь нэг үндэс x 1 байна
Эхний шатанд x 0 =(a+b)/2-ийг тооцоолно
Дараа нь энэ цэг дэх функцийн утгыг тодорхойлно: хэрэв f(x 0) бол< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.
b-a зөрүү нь шаардлагатай алдаанаас бага байх үед тооцоолол зогсдог.
Хагас хуваах аргыг жишээ болгон бид x 3 -3*x+1=0 тэгшитгэлийн интервал дээр 10 -3 нарийвчлалтайгаар үндсийг олох болно.
Хүснэгтээс харахад үндэс нь 0.347 байна. Давталтын тоо 10. Гүйцэтгэх нөхцөл: a-b=0.0009< 10 -3
Хагаслах арга буюу дихотоми аргань тоон аргыг ашиглан тэгшитгэлийг шийдвэрлэх хамгийн энгийн арга юм.
Татаж авах:
Дихотоми аргыг ашиглан тэгшитгэлийг шийдвэрлэх - Паскаль хэл дээр хоёр хэсэгт хуваах аргыг ашиглан тэгшитгэлийг шийдвэрлэх.
Маш тодорхой теорем байдаг: "Хэрэв тодорхой интервалын төгсгөлд байгаа тасралтгүй функц нь өөр өөр тэмдгийн утгатай бол энэ интервалын дотор үндэс (дор хаяж нэг, гэхдээ хэд хэдэн) байна.". Энэ теорем дээр үндэслэн функцийн язгуурын ойролцоо утгыг тоон аргаар тодорхойлохыг байгуулна. Ерөнхийдөө энэ аргыг нэрлэдэг дихотоми, өөрөөр хэлбэл сегментийг хоёр хэсэгт хуваах. Ерөнхий алгоритм нь дараах байдалтай байна.
Шаардлагатай нарийвчлалд хүрэх хүртэл.
Дихотомийн аргын хувилбарууд нь хуваах цэгийг сонгохдоо ялгаатай байдаг. Дихотомийн хувилбаруудыг авч үзье: хагас хуваах аргаТэгээд хөвчний арга.
Хагас хуваах арга
Хагас хуваах аргагэж бас нэрлэдэг хуваах арга. Энэ аргын хувьд интервалыг яг хагасаар хуваана.
Энэ арга нь функцийн нарийн төвөгтэй байдлаас үл хамааран аргын баталгаатай нийлэлтийг баталгаажуулдаг бөгөөд энэ нь маш чухал шинж чанар юм. Аргын сул тал нь адилхан - арга нь хэзээ ч хурдан нийлэхгүй, өөрөөр хэлбэл. Аргын нэгдэл нь хамгийн муу тохиолдлын нэгдэлтэй үргэлж тэнцүү байдаг.
Хагас хуваах арга:
- Хайлт хийх хамгийн энгийн аргуудын нэг нэг аргументийн функцын үндэс.
- олоход ашигладаг бодит үнэ цэнэтэй функцийн утгууд, зарим шалгуураар тодорхойлогддог (энэ нь харьцуулалт байж болно хамгийн бага, дээд тал ньэсвэл тодорхой тоо).
Хагас хуваах арга нь функцийн үндсийг олох арга юм
Аргын тухай мэдэгдэл
Функцийн үндсийг олох аргыг ашиглахын өмнө мэддэг аргуудын аль нэгийг, жишээлбэл, график аргыг ашиглан үндсийг нь салгах шаардлагатай. Үндэсийг аль сегментээс хайх ёстойг мэдэхгүй бол үндсийг нь салгах шаардлагатай.
Функцийн үндэс нь сегмент дээр тусгаарлагдсан гэж бид таамаглах болно. Даалгавар нь энэ үндсийг хоёр хэсэгт хуваах аргыг ашиглан олж, боловсронгуй болгох явдал юм. Өөрөөр хэлбэл, өгөгдсөн нарийвчлалтайгаар язгуурын ойролцоо утгыг олох хэрэгтэй.
Функц нь сегмент дээр тасралтгүй байг,
ба тэгшитгэлийн цорын ганц үндэс юм.(Бид сегмент дээр хэд хэдэн үндэс, өөрөөр хэлбэл нэгээс олон үндэс байгаа тохиолдолд авч үзэхгүй. Бид бас өөр хангалттай бага эерэг тоог авч болно, жишээ нь, .)
Сегментийг хагасаар хуваая. Бид нэг цэг ба хоёр сегментийг авдаг.
Бид шинэ сегментийг хагасаар хуваадаг. Бид энэ сегментийн дунд хэсгийг авдаг гэх мэт.0" alt=" \eps >0) нарийвчлалтай язгуурын ойролцоо утгыг олохын тулд">, необходимо остановить процесс половинного деления на таком шаге , на котором и вычислить . Тогда можно взять .!}
С++ хэл дээрх аргын хэрэгжилт ба тоон жишээ
Хагас хуваах аргыг ашиглан тэгшитгэлийг шийдье. График аргабид хүссэн үндэс хамаарах сегментийг олдог. Учир нь бид хүлээн зөвшөөрч байна.
Асуудлыг шийдэх C++ програмын жишээг доор харуулав.
Програм 1. Тэгшитгэлийн үндэс
#оруулна
Таны хайж буй үндэс. Тооцооллыг нарийвчлалтай хийсэн.
Завсрын тооцоог доорх хүснэгтэд үзүүлэв.
| n | a n | б н | c n | b n -c n |
|---|---|---|---|---|
| 1 | 0 | 1 | 0.5 | 0.5 |
| 2 | 0.5 | 1 | 0.75 | 0.25 |
| 3 | 0.75 | 1 | 0.875 | 0.125 |
| 4 | 0.875 | 1 | 0.9375 | 0.0625 |
| 5 | 0.875 | 0.9375 | 0.90625 | 0.03125 |
| 6 | 0.875 | 0.90625 | 0.890625 | 0.015625 |
| 7 | 0.875 | 0.890625 | 0.8828125 | 0.0078125 |
Хагас хуваах аргыг оновчтой болгох арга
Нэг параметрийн оновчлол (нэг хувьсагчийн функцүүдийн экстремумыг хайх) нь бие даасан бөгөөд байнга тулгардаг ажил юм. Нэмж дурдахад илүү төвөгтэй асуудал багасдаг - олон хувьсагчийн функцийн экстремумыг олох.
Хагас хуваах аргыг хамгийн энгийн нэг параметртэй болзолгүй оновчлолын арга гэж үзье. Энэ арга нь шууд хайлтын арга. Үүний дотор зорилгын функцийн экстремумыг хайхдаа зөвхөн зорилгын функцийн тооцоолсон утгыг ашигладаг.
Функцийг өгсөн. Өгөгдсөн нарийвчлалтайгаар интервал дээрх функцын хамгийн бага (эсвэл хамгийн их) утгыг олох шаардлагатай. олох
.Аргын аман алгоритмыг бичье.
Аргын алгоритмын диаграммыг 2-р зурагт үзүүлэв.
- тогтмол,Гарах үед – функц хамгийн бага (эсвэл хамгийн их) байх цэгийн координат, – энэ цэг дэх функцийн утга.
Хөвчний арга
Сегментийг хагас болгон хуваах сул тал нь хазайлтыг (үнэмлэхүй утга) үл тоомсорлож, зөвхөн функцийн тэмдгийг ашигладагтай холбоотой юм. Гэхдээ функцийн утга бага байх тусам (үнэмлэхүй утгаар) бид язгуурт ойртох нь ойлгомжтой. Хөвчний аргасегментийн ирмэгээс байрлах цэг дээр сегментийг ирмэг дэх функцийн үнэмлэхүй утгатай пропорциональ байдлаар хуваахыг санал болгож байна. ("Хөвч арга" гэсэн нэр нь хуваагдлын цэг нь абсцисса тэнхлэгтэй огтлолцох хэсэг болох хөвчийг хэлснээс үүдэлтэй.)
Аргын тухай мэдэгдэл
Энэ арга нь хайлтын алхам бүрт функцийг хөвчөөр солиход суурилдаг бөгөөд тэнхлэгтэй огтлолцох нь язгуурын ойролцоо утгыг өгдөг.
Энэ тохиолдолд хайлтын явцад хөвчний гэр бүлийг байгуулж болно.
Үүний үр дүнд үндэс рүү ойртох давтагдах үйл явц нь давтагдах томъёогоор хэрэгждэг.
- a тохиолдолд):
- b тохиолдолд):
Хайлтын үйл явц нь нөхцөл байдал биелэх хүртэл үргэлжилнэ.
Энэ арга нь %200" alt="f(z)\cdot f бол хурдан нийлэлтийг хангадаг.""(z) > 0">, т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.!}
Хөвчний аргыг ашиглан үндсийг боловсронгуй болгох алгоритмын диаграммыг Зураг дээр үзүүлэв. 4.
Хөвчний арга ба хуваах аргын хослол
Хөвчний аргыг хоёр хэсэгт хуваах арга нь шаардлагатай нарийвчлалыг баталгаажуулсны дараа "дуусгах" болгон ашиглаж болно - энэ нь баталгаатай нарийвчлалыг мэдэгдэхүйц сайжруулахгүй, харин шийдлийн нарийвчлалыг хэд хэдэн дарааллаар нэмэгдүүлэх магадлалтай.
Үүнийг мөн дихотомийн арга гэж нэрлэдэг. Тэгшитгэлийг шийдвэрлэх энэ арга нь дээр дурдсан аргуудаас ялгаатай нь эхний болон хоёр дахь деривативууд интервал дээр тэмдэгээ хадгалах нөхцөлийг биелүүлэх шаардлагагүй юм. Хагалах арга нь ямар ч үргэлжилсэн f(x), түүний дотор дифференциалагдахгүй функцүүдэд нийлдэг.
Сегментийг цэгээр хагасаар хуваа. Хэрэв (энэ нь бараг хамгийн их магадлалтай) бол хоёр тохиолдол боломжтой: f(x) сегмент дээрх тэмдгийг өөрчилнө (Зураг 3.8), эсвэл сегмент дээр (Зураг 3.9)
Тухайн тохиолдол бүрт функцийн тэмдэг өөрчлөгдөх сегментийг сонгож, хоёр дахин багасгах үйл явцыг үргэлжлүүлснээр тэгшитгэлийн язгуурыг агуулсан дурын жижиг сегментэд хүрч болно.
Жишээ 4. 5x - 6x -3 = 0 тэгшитгэл нь интервал дээр нэг язгууртай. Энэ тэгшитгэлийг хагас хуваах аргыг ашиглан шийд.
Шийдэл: Паскаль програм нь дараах байдлаар харагдаж болно.
функц f(x: бодит): бодит;
f:=exp(x*ln(5))-6*x-3;
a, b, e, c, x: бодит;
харин abs(b-a)>e хийх
хэрэв f(a)*f(c)<0 then
writeln("x=",x:3:3," f(x)=",f(x):4:4);
Програмын гүйцэтгэлийн үр дүн:
e=0.001 x=1.562 f(x)=-0.0047
20. Хагас хуваах аргын алгоритм.
1.Шинэ язгуурын ойролцоо утгыг тодорхойлох Xсегментийн дунд [a,b]: x=(a+b)/2.
2. Цэг дэх функцийн утгыг ол АТэгээд X: F(a)Тэгээд F(x).
3. Нөхцөл байдлыг шалгана уу F(a)*F(x)< 0 . Хэрэв нөхцөл хангагдсан бол үндэс нь сегмент дээр байрлана [Өө] бцэг рүү шилжих x (b=x). Хэрэв нөхцөл хангагдаагүй бол үндэс нь сегмент дээр байрлана [x,b]. Энэ тохиолдолд танд цэг хэрэгтэй Ацэг рүү шилжих x (a=x).
4. 1-р алхам руу очоод сегментийг дахин хагасаар хуваа. Алгоритм нь нөхцөл биелэх хүртэл үргэлжилнэ /F(x)/< e (заасан нарийвчлал).
21. Үндэс олох энгийн давталтын арга. Геометрийн тайлбар.
Анхны тэгшитгэл f(x)=0 нь зүүн талд нь үл мэдэгдэх нь сонгогдсон хэлбэрт эквивалент хувиргалтаар буурдаг, өөрөөр хэлбэл x=φ(x), энд φ(x) нь анхны f функцтэй холбоотой зарим функц юм. (x). Тэгшитгэлийг бичих энэ хэлбэр нь анхны ойролцоолсон x 0-ийг өгснөөр дараагийн, эхлээд x 1 =φ(x 0) ойролцоо, дараа нь x 2 =φ(x 1) гэсэн хоёр дахь ойролцооллыг олж авах боломжийг олгодог x n +1 гэх мэт. =φ(x n)… . (x n )= x 0, x 1, x 2, …, x n,… гэсэн дарааллыг x 0 анхны утга бүхий давталтын дараалал буюу ойролцоолсон дараалал гэнэ. Хэрэв φ(x) функц тасралтгүй биш бөгөөд хязгаар байгаа бол ξ = lim x n-ийг n→∞ гэж үзвэл, x n +1 =φ(x n) тэгшитгэлийн хязгаар руу шилжвэл n→ ∞: lim x n +1 =lim φ(x n)=φ(lim x n) болохыг олж мэднэ. ), өөрөөр хэлбэл, ξ=φ(ξ) Иймээс хэрвээ ойртсон тоонуудын дараалал нийлбэл тэгшитгэлийн язгуурт нийлнэ, улмаар (1) тэгшитгэл болно. Давталтын процессын нэгдлээс шалтгаалан энэ үндсийг хангалттай томоор тооцоолж болно nөгөгдсөн нарийвчлалтайгаар. Гэхдээ ямар нөхцөлд дараалал (x n) нийлэхийг тодорхойлох шаардлагатай. ε n ба ε n +1 гэсэн хоёр хөршийн ойролцоо тооцооллын алдааны хоорондох холболтыг олж авъя: x n =ξ+ε n, x n +1 =ξ+ε n +1. Эдгээр дүрслэлийг x n +1 =φ(x n) гэж орлуулж, функцийг язгуурын ойролцоох Тейлорын цуваа болгон өргөжүүлье:ξ+ε n +1 =φ(ξ+ε n)=φ(ξ)+ε n. φ'(ξ)+ (ε n 2 /2!)φ''(η), энд η О [ξ; ξ+ε n ] М ξ нь үндэс учир ξ=φ(ξ) , ε n +1 =ε n φ'(ξ)+(φ''(η)/2)ε n 2 болно. ε оноос хойш<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n|ε n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.
Энгийн давталтын аргын нэгдэх тухай теорем.ξ-ийг x=φ(x) тэгшитгэлийн язгуур гэж үзье, φ(x) функц тодорхойлогдсон бөгөөд интервал дээр дифференциалагдах ба x О-ийн хувьд φ (x) О функцийн бүх утгууд байна. Тэгвэл ийм эерэг тоо байвал q<1, что при x Î выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x n +1 =φ(x n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x 0 Î .Таким образом, последовательность {x n },начинающаяся с любого x 0 Î , сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ'(x)>-1, тэгвэл зэргэлдээх ойролцоо тоонууд нь язгуурын эсрэг талд байрладаг - ийм нийлэлтийг хоёр талын (эсвэл спираль) гэж нэрлэдэг - 2-р зураг. Энэ тохиолдолд үндэс нь интервалд агуулагдах тул төгсгөлүүд нь ойролцоох ойролцоо утгатай - ξÎ(x n ,x n +1), дараа нь нөхцөлийн биелэлт |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.
Давталтын аргуудыг нэгтгэх хурдны хувьд харьцуулахын тулд дараахь ойлголтуудыг танилцуулав.
Тодорхойлолт 1:Дарааллын (x n) ξ-д нийлэхийг нэрлэнэ шугаман(үүний дагуу давтагдах үйл явц нь шугаман конвергенц), хэрэв CO(0,1) тогтмол ба n 0 тоо байвал |ξ-x n +1 |≤C|ξ-x n | n≥n 0-ийн хувьд.
Өмнө оруулсан алдаануудын хувьд энэ нь |ε n+1 |≤C|ε n | гэсэн утгатай. Энгийн давталтын аргын хувьд тогтмол С нь q утга, өөрөөр хэлбэл арга нь шугаман нийлдэг.
Тодорхойлолт 2:Ойролцоо (x n ) дараалал нь хамгийн багадаа ξ-д нийлдэг Р--р дараалал (үүний дагуу давтагдах үйл явц нь дор хаяж байна х--р дараалал), хэрэв ийм тогтмол C>0 байвал, х≥1 ба n 0 , бүх n≥n 0-ийн хувьд |ξ-x n +1 |≤C|ξ-x n | p (эсвэл бусад тэмдэглэгээнд |ε n+1 |≤C|ε n | p).
