Далее: Описание этапов проведения лабораторной Вверх: Лабораторная работа № 2 Назад: Лабораторная работа № 2

Теоретический аспект

В силу сложности структуры символьной записи алгебраических и трансцендентных уравнений задача по нахождению точных решений является весьма трудоемкой и подчас не реальной.

Процедура нахождения приближенных решений алгебраических и трансцендентных уравнений может быть реализована в два этапа:

Локализация корней - выделение отрезков, каждый из которых содержит по одному корню, с использованием аналитических или графических методов.

Уточнение корней - вычисление приближенных значений действительных корней уравнения на каждом из отрезков с необходимой точностью, при этом каждый из корней в силу единственности на рассматриваемом интервале, называемом интервалом изоляции корня, является изолированным, с использованием численных методов.

Предлагаемые в рамках данной лабораторной работы численные методы используются для приближенных решений алгебраических и трансцендентных уравнений вида $f(x_n ) = 0$ с целью определения приближенного значения изолированного действительного корня $x_n$ на отрезке $[a_0 ,b_0 ]$ с необходимой точностью $\varepsilon$.

Рассмотрим логические основы реализации метода дихотомии (бисекции), комбинированного метода хорд и касательных (Ньютона), метода итераций для выполнения приближенных решений алгебраических и трансцендентных уравнений в зависимости от различных значений $a_0$, $b_0$, $\varepsilon$, заложенных в программу "APROXEQU".

Метод дихотомии (бисекции)

Суть дихотомии (бисекции) или половинного деления состоит в следующем: если разделить отрезок C на отрезки A и B таким образом, что это будет отражать дихотомию, то C, деленное на A, будет равно C, деленному на B, то есть A равно B: $\frac{C}{A} = \frac{С}{B} = 2$ или $A = B$.

Таким образом, при наличии исходного отрезка $\left[ {a_0 ,b_0 } \right]$ полученный в результате "N"-го деления отрезок $\left[ {a_N ,b_N } \right]$ связан с исходным соотношением $b_N - a_N = \frac{b_0 - a_0 }{2^N}$.

В данной лабораторной работе метод дихотомии (бисекции) ("METHOD OF DICHOTOMY") имеет следующую реализацию:

Итерация с индексом $''0''$:

На искомом отрезке $\left[ {a_0^D ,b_0^D } \right]$ при соблюдении условий $a_0^D < b_0^D$ и $f\left( {a_0^D } \right) \cdot f\left( {b_0^D } \right) < 0$ выбирается точка $x_0^D$, исходя из неравенства $a_0^D < x_0^D < b_0^D$, в соответствии с принципами дихотомии согласно следующему соотношению: $x_0^D = \frac{a_0^D + b_0^D }{2}$.

Если достигнута истинность выражения $\left\vert {b_0^D - a_0^D } \right\vert \le 2\varepsilon$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^D = 0$, и в качестве приближенного значения действительного корня уравнения $x_\varepsilon ^D$ выбирается $x_\varepsilon ^D = x_0^D$ в силу равенства $x_0^D = \frac{a_0^D + b_0^D }{2}$.

Если $\left\vert {b_0^D - a_0^D } \right\vert > 2\varepsilon$, то осуществляется переход к следующей итерации.

Итерация с индексом $''N'' \quad \left( {N \ge 1} \right)$:

Если $f\left( {x_{N - 1}^D } \right) \cdot f\left( {a_{N - 1}^D } \right) < 0$ и $f\left( {x_{N - 1}^D } \right) \cdot f\left( {b_{N - 1}^D } \right) > 0$, то $a_N^D = a_{N - 1}^D$, $b_N^D = x_{N - 1}^D$, $b_N^D - a_N^D = x_{N - 1}^D - a_{N - 1}^D = \frac{b_{N - 1}^D - a_{N - 1}^D }{2}$, и получаем отрезок $\left[ {a_N^D ,b_N^D } \right] = \left[ {a_{N - 1}^D ,x_{N - 1}^D } \right]$.

Если $f\left( {x_{N - 1}^D } \right) \cdot f\left( {a_{N - 1}^D } \right) > 0$ и $f\left( {x_{N - 1}^D } \right) \cdot f\left( {b_{N - 1}^D } \right) < 0$, то $a_N^D = x_{N - 1}^D$, $b_N^D = b_{N - 1}^D$, $b_N^D - a_N^D = b_{N - 1}^D - x_{N - 1}^D = \frac{b_{N - 1}^D - a_{N - 1}^D }{2}$, и получаем отрезок $\left[ {a_N^D ,b_N^D } \right] = \left[ {x_{N - 1}^D ,b_{N - 1}^D } \right]$.

На отрезке $\left[ {a_N^D ,b_N^D } \right]$ при соблюдении условий $a_N^D < b_N^D$ и $f\left( {a_N^D } \right) \cdot f\left( {b_N^D } \right) < 0$ выбирается точка $x_N^D$, исходя из неравенства $a_N^D < x_N^D < b_N^D$, в соответствии с принципами дихотомии согласно следующему соотношению: $x_N^D = \frac{a_N^D + b_N^D }{2}$.

Если достигнута истинность выражения $\left\vert {b_N^D - a_N^D } \right\vert \le 2\varepsilon$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^D = N$, и в качестве приближенного значения действительного корня уравнения $x_\varepsilon ^D$ выбирается $x_\varepsilon ^D = x_N^D$ в силу равенства $x_N^D = \frac{a_N^D + b_N^D }{2}$.

Если $\left\vert {b_N^D - a_N^D } \right\vert > 2\varepsilon$, то осуществляется переход к следующей итерации.

Комбинированный метод хорд и касательных (Ньютона)

Комбинированный метод хорд и касательных (Ньютона) применяется только в случаях, когда функция $f\left( x \right)$ на искомом отрезке $\left[ {a_0 ,b_0 } \right]$ монотонна и не имеет точек перегиба, то есть ${f}'\left( x \right)$ и ${f}''\left( x \right)$ не изменяют знака на отрезке $\left[ {a_0 ,b_0 } \right]$.

Суть метода заключается в сжатии искомого отрезка $\left[ {a_0 ,b_0 } \right]$ в силу проведения из противоположных концов хорды и касательной согласно следующим правилам:

Для случая $f\left( {a_0 } \right) \cdot {f}''\left( {a_0 } \right) > 0$ и $f\left( {b_0 } \right) \cdot {f}''\left( {b_0 } \right) < 0$ отрезок $\left[ {a_N ,b_N } \right]$ образуется из отрезка $\left[ {a_{N - 1} ,b_{N - 1} } \right]$ согласно следующим правилам:

Исходя из уравнения касательной, проходящей из точки с координатами $\left( {a_{N - 1} ,f\left( {a_{N - 1} } \right)} \right)$ к графику исходной функции $f\left( x \right)$, то есть $f_1 \left( {a_N } \right) = f(a_{N - 1} ) + {f}'(a_{N - 1} ) \cdot (a_N - a_{N - 1} )$, получим абсциссу точки пересечения касательной с осью абсцисс ( $f_1 \left( {a_N } \right) = 0)$: $a_N = a_{N - 1} - \frac{f\left( {a_{N - 1} } \right)}{{f}'\left( {a_{N - 1} } \right)}$.

Исходя из уравнения хорды, проходящей через точки с координатами $\left( {a_{N - 1} ,f\left( {a_{N - 1} } \right)} \right)$ и $\left( {b_{N - 1} ,f\left( {b_{N - 1} } \right)} \right)$, то есть $f_2 \left( {b_N } \right) = f\left( {b_{N - 1} } \right) + \left( {b_N - b_{N -... ...t( {a_{N - 1} } \right) - f\left( {b_{N - 1} } \right)}{a_{N - 1} - b_{N - 1} }$, получим абсциссу точки пересечения хорды с осью абсцисс ( $f_2 \left( {b_N } \right) = 0)$: $b_N = b_{N - 1} - f(b_{N - 1} ) \cdot \frac{a_{N - 1} - b_{N - 1} }{f(a_{N - 1} ) - f(b_{N - 1} )}$.

Для случая $f\left( {a_0 } \right) \cdot {f}''\left( {a_0 } \right) < 0$ и $f\left( {b_0 } \right) \cdot {f}''\left( {b_0 } \right) > 0$ отрезок $\left[ {a_N ,b_N } \right]$ образуется из отрезка $\left[ {a_{N - 1} ,b_{N - 1} } \right]$ согласно следующим правилам:

Исходя из уравнения касательной, проходящей из точки с координатами $\left( {b_{N - 1} ,f\left( {b_{N - 1} } \right)} \right)$ к графику исходной функции $f\left( x \right)$, то есть $f_1 \left( {b_N } \right) = f(b_{N - 1} ) + {f}'(b_{N - 1} ) \cdot (b_N - b_{N - 1} )$, получим абсциссу точки пересечения касательной с осью абсцисс ( $f_1 \left( {b_N } \right) = 0)$: $b_N = b_{N - 1} - \frac{f\left( {b_{N - 1} } \right)}{{f}'\left( {b_{N - 1} } \right)}$.

Исходя из уравнения хорды, проходящей через точки с координатами $\left( {a_{N - 1} ,f\left( {a_{N - 1} } \right)} \right)$ и $\left( {b_{N - 1} ,f\left( {b_{N - 1} } \right)} \right)$, то есть $f_2 \left( {a_N } \right) = f\left( {a_{N - 1} } \right) + \left( {a_N - a_{N -... ...t( {b_{N - 1} } \right) - f\left( {a_{N - 1} } \right)}{b_{N - 1} - a_{N - 1} }$, получим абсциссу точки пересечения хорды с осью абсцисс ( $f_2 \left( {a_N } \right) = 0)$: $a_N = a_{N - 1} - f(a_{N - 1} ) \cdot \frac{b_{N - 1} - a_{N - 1} }{f(b_{N - 1} ) - f(a_{N - 1} )}$.

В данной лабораторной работе комбинированный метод хорд и касательных ("METHOD OF CHORDS AND TANGENTS") или метод Ньютона имеет следующую реализацию:

Итерация с индексом $''0''$:

На искомом отрезке $\left[ {a_0^{CT} ,b_0^{CT} } \right]$ при соблюдении условий $a_0^{CT} < b_0^{CT}$, $f\left( {a_0^{CT} } \right) \cdot f\left( {b_0^{CT} } \right) < 0$, ${f}'\left( {a_0^{CT} } \right) \cdot {f}''\left( {a_0^{CT} } \right) > 0$, ${f}'\left( {b_0^{CT} } \right) \cdot {f}''\left( {b_0^{CT} } \right) > 0$ выбирается точка с координатами $\left( {x_0^{CT} ,f\left( {x_0^{CT} } \right)} \right)$, из которой проводится первая касательная к графику исходной функции $f\left( x \right)$.

Если $f\left( {a_0^{CT} } \right) \cdot {f}''\left( {a_0^{CT} } \right) > 0$ и $f\left( {b_0^{CT} } \right) \cdot {f}''\left( {b_0^{CT} } \right) < 0$, то $x_0^{CT} = a_0^{CT}$.

Если $f\left( {a_0^{CT} } \right) \cdot {f}''\left( {a_0^{CT} } \right) < 0$ и $f\left( {b_0^{CT} } \right) \cdot {f}''\left( {b_0^{CT} } \right) > 0$, то $x_0^{CT} = b_0^{CT}$.

Если достигнута истинность выражения $\left\vert {b_0^{CT} - a_0^{CT} } \right\vert \le 2\varepsilon$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^{CT} = 0$, и в качестве приближенного значения действительного корня уравнения $x_\varepsilon ^{CT}$ выбирается $x_\varepsilon ^{CT} = \frac{a_0^{CT} + b_0^{CT} }{2}$.

Если $\left\vert {b_0^{CT} - a_0^{CT} } \right\vert > 2\varepsilon$, то осуществляется переход к следующей итерации.

Итерация с индексом $''N'' \left( {N \ge 1} \right)$:

Если $x_0^{CT} = a_0^{CT}$, то на отрезке $\left[ {a_{N - 1}^{CT} ,b_{N - 1}^{CT} } \right]$ выбираются точки $a_N^{CT}$ и $b_N^{CT}$ с соблюдением условия $a_{N - 1}^{CT} < a_N^{CT} < b_N^{CT} < b_{N - 1}^{CT}$ согласно следующим соотношениям:

$$a_N^{CT} = a_{N - 1}^{CT} - \frac{f\left( {a_{N - 1}^{CT} } ... ...a_{N - 1}^{CT} } \right) - f\left( {b_{N - 1}^{CT} } \right)}.$$

Если $x_0^{CT} = b_0^{CT}$, то на отрезке $\left[ {a_{N - 1}^{CT} ,b_{N - 1}^{CT} } \right]$ выбираются точки $a_N^{CT}$ и $b_N^{CT}$ с соблюдением условия $a_{N - 1}^{CT} < a_N^{CT} < b_N^{CT} < b_{N - 1}^{CT}$ согласно следующим соотношениям:

$$b_N^{CT} = b_{N - 1}^{CT} - \frac{f\left( {b_{N - 1}^{CT} } ... ...b_{N - 1}^{CT} } \right) - f\left( {a_{N - 1}^{CT} } \right)}.$$

Если достигнута истинность выражения $\left\vert {b_N^{CT} - a_N^{CT} } \right\vert \le 2\varepsilon$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^{CT} = N$, и в качестве приближенного значения действительного корня уравнения $x_\varepsilon ^{CT}$ выбирается $x_\varepsilon ^{CT} = \frac{a_N^{CT} + b_N^{CT} }{2}$.

Если $\left\vert {b_\varepsilon ^{CT} - a_\varepsilon ^{CT} } \right\vert > 2\varepsilon$, то осуществляется переход к следующей итерации.

Метод итераций

Метод итераций применяется к уравнению вида $x = g\left( x \right)$ на отрезке $\left[ {a_0 ,b_0 } \right]$ при соблюдении условий $\left\vert {{g}'\left( x \right)} \right\vert < q < 1$ и $a_0 \le g\left( x \right) \le b_0$, где $x \in \left[ {a_0 ,b_0 } \right]$.

Суть метода итераций заключается в построении рекуррентной последовательности действительных чисел, сходящихся к решению, по формуле $x_N = g(x_{N - 1} )$, где $x \in \left[ {a_0 ,b_0 } \right]$.

Обозначим дифференцируемую функцию $f\left( x \right) = x - g\left( x \right)$, при этом за начальное приближение корня примем произвольное значение $x_0 \in \left[ {a_0 ,b_0 } \right]$.

$$\left\vert {{f}'\left( x \right)} \right\vert = \left\vert {... ...e 1 - \left\vert {{g}'\left( x \right)} \right\vert \ge 1 - q.$$

Если $\bar {x}$ - точное решение уравнения $f\left( \bar {x} \right) = 0$, то имеем:

$$\left\vert {x_{N + 1} - x_N } \right\vert = \left\vert {g\le... ...\left( \bar {x} \right) - f\left( {x_N } \right)} \right\vert.$$

По теореме Лагранжа $\left\vert {{f}'\left( \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\fr... ... f\left( {x_N } \right)} \right\vert}{\left\vert {\bar {x} - x_N } \right\vert}$, где $\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}}\over {x}} \in \left[ {\bar {x},x_N } \right]$.

Тогда $\left\vert {x_{N + 1} - x_N } \right\vert = \left\vert {{f}'\left( \mathord{\bu... ...\vert \ge \left( {1 - q} \right) \cdot \left\vert {\bar {x} - x_N } \right\vert$.

С другой стороны, так как $x_{N + 1} = g\left( {x_N } \right)$, $x_N = g\left( {x_{N - 1} } \right)$, $x_{N - 1} = g\left( {x_{N - 2} } \right)$, то получим: $\left\vert {x_{N + 1} - x_N } \right\vert = \left\vert {g\left( {x_N } \right) - g\left( {x_{N - 1} } \right)} \right\vert$.

По теореме Лагранжа $\left\vert {{g}'\left( \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\sm... ...( {x_{N - 1} } \right)} \right\vert}{\left\vert {x_N - x_{N - 1} } \right\vert}$, где $\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\smile$}}\over {x}} \in \left[ {x_{N - 1} ,x_N } \right]$.

Тогда $\left\vert {x_{N + 1} - x_N } \right\vert = \left\vert {{g}'\left( \mathord{\bu... ...- x_{N - 1} } \right\vert \le q \cdot \left\vert {x_N - x_{N - 1} } \right\vert$.

Очевидно, что $\left\vert {x_{N + 1} - x_N } \right\vert \le q \cdot \left\vert {x_N - x_{N - ... ... 1} - x_{N - 2} } \right\vert \le q^N \cdot \left\vert {x_1 - x_0 } \right\vert$.

Каждый из членов ряда $x_0 + \left( {x_1 - x_0 } \right) + \left( {x_2 - x_1 } \right) + ... + \left( {x_N - x_{N - 1} } \right) + ...$, как следует из неравенства, не превосходит $q$, а поскольку знаменатель геометрической прогрессии $q < 1$, то в силу сходимости данной геометрической прогрессии рассматриваемый ряд сходится к необходимому решению.

Так как $\left\vert {x_{N + 1} - x_N } \right\vert \ge \left( {1 - q} \right) \cdot \left\vert {\bar {x} - x_N } \right\vert$ и $\left\vert {x_{N + 1} - x_N } \right\vert \le q \cdot \left\vert {x_N - x_{N - 1} } \right\vert$, а также согласно неравенству $\varepsilon < \left\vert {\bar {x} - x_N } \right\vert$, получим, что $\left( {1 - q} \right) \cdot \left\vert {\bar {x} - x_N } \right\vert \le q \cdot \left\vert {x_N - x_{N - 1} } \right\vert$ или $\left\vert {x_N - x_{N - 1} } \right\vert \ge \frac{1 - q}{q} \cdot \left\vert {\bar {x} - x_N } \right\vert$, то есть $\left\vert {x_N - x_{N - 1} } \right\vert > \frac{1 - q}{q} \cdot \varepsilon$.

В данной лабораторной работе метод итераций ("METHOD OF ITERATIONS") имеет следующую реализацию:

Итерация с индексом $''0''$:

На искомом отрезке $\left[ {a_0^I ,b_0^I } \right]$ при соблюдении условий $a_0^I < b_0^I$ и $f\left( {a_0^I } \right) \cdot f\left( {b_0^I } \right) < 0$ осуществляется ввод в символьном виде уравнения функции $y = g(x)$, исходя из уравнения $x = g(x)$ и неравенства $a_0^I \le g(x_N^I ) \le b_0^I$.

Осуществляется ввод значения знаменателя геометрической прогрессии $q$, исходя из условия $\left\vert {{g}'(x_N^I )} \right\vert < q < 1$.

На искомом отрезке $\left[ {a_0^I ,b_0^I } \right]$ при соблюдении условий $a_0^I < b_0^I$ и $f\left( {a_0^I } \right) \cdot f\left( {b_0^I } \right) < 0$ выбирается абсцисса точки начального приближения с координатами $\left( {x_0^I ,f\left( {x_0^I } \right)} \right)$, исходя из неравенства $a_0^I < x_0^I < b_0^I$.

Итерация с индексом $''N'' \left( {N \ge 1} \right):$

Устанавливается значение абсциссы точки с координатами $\left( {x_N^I ,f\left( {x_N^I } \right)} \right)$ при соблюдении условия $a_0^I < x_N^I < b_0^I$, исходя из соотношения $x_N^I = g(x_{N - 1}^I )$.

Если достигнута истинность выражения $\left\vert {x_N^I - x_{N - 1}^I } \right\vert \le \frac{1 - q}{q} \cdot \varepsilon$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^I = N$, и в качестве приближенного значения действительного корня уравнения $x_\varepsilon ^I$ выбирается значение $x_\varepsilon ^I = x_N^I$.

Если $\left\vert {x_N^I - x_{N - 1}^I } \right\vert > \frac{1 - q}{q}\varepsilon$, то осуществляется переход к следующей итерации.

Далее: Описание этапов проведения лабораторной Вверх: Лабораторная работа № 2 Назад: Лабораторная работа № 2