semopt11 (Практические занятия)

Занятие 11. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХУРАВНЕНИЙПОСТАНОВКА ЗАДАЧИПусть дано нелинейное уравнениеf (x ) = 0 ,(*)где f (x ) – функция, определенная и непрерывная на некотором промежутке.Этапы решения нелинейных уравненийПервый этап. Находятся отрезки [ai , bi ] , внутри каждого из которых содержитсяодин простой или кратный корень ( x ∗i ∈ [ai , bi ] ). Этот этап называется процедуройотделения корней. По сути, на нем осуществляется грубое нахождение корней x ∗i .Второй этап.

Грубое значение каждого корня x ∗i уточняется до заданной точности одним из численных методов, в которых реализуются последовательные приближения.А. МЕТОД ПРОСТЫХ ИТЕРАЦИЙМетодика решения задачиШаг 1. Уравнение f (x ) = 0 равносильным преобразованием привести к видуx = ϕ( x ) . Это преобразование может быть осуществлено различными путями, но длясходимости нужно обеспечить выполнение условия ϕ′( x ) ≤ χ < 1 ( χ – некоторая константа). При этом задача сводится к нахождению абсциссы точки пересечения прямойy = x и кривой y = ϕ( x ) (рис. 1).yy=xy = ϕ( x )0x∗Рис.

1231xШаг 2. Задать начальное приближение x (0 ) ∈ [a, b ] и малое положительное числоε . Положить k = 0 .Шаг 3. Вычислить следующее приближение:x ( k +1) = ϕ( x ( k ) ) .Шаг 4. Еслиx ( k +1) − x ( k ) ≤ ε , итерации завершаются и x ∗ ≅ x (k +1) . Еслиx ( k +1) − x ( k ) > ε , положить k = k + 1 и перейти к п.3.Способы преобразования уравненияПреобразование уравнения f ( x ) = 0 к равносильному виду x = ϕ( x ) может бытьвыполнено неоднозначно.1.

Можно заменить уравнение f ( x ) = 0 на равносильное x = x + c f ( x ) , гдеc = const ≠ 0 . Тогда, принимая правую часть этого уравнения за ϕ( x ) и раскрываяϕ′( x ) = 1 + c f ′( x ) < 1 , получаем условие − 2 < c f ′( x ) < 0 .2. Можно выразить x из уравнения f ( x ) = 0 так, чтобы для полученного уравнения x = ϕ(x ) выполнялось условие сходимости ϕ′( x ) < 1 в окрестности искомого корня.Пример 1.

Найти решение уравнения x 3 − x + 1 = 0 методом простых итераций сточностью ε1 = 0,01 и ε 2 = 0,001 .† I. Отделим корень уравнения. Уравнение имеет три корня, среди которых покрайней мере один действительный, поскольку это уравнение нечетной степени.Преобразуем уравнение к равносильному виду: x 3 = x − 1 и найдем точки пересечения графиков y = x 3 и y = x − 1 (рис.

2).yy = x3y = x −1−2−101−1Рис. 2232xОчевидно, корень уравнения x ∗ ∈ [ − 2; − 1 ] .II. Преобразуем уравнение к виду x = ϕ( x ) . Для этого запишем его сначала в форме x = x 3 + 1 . Легко показать, что функция ϕ( x ) = x 3 + 1 не удовлетворяет условию сходимости, поскольку ϕ′( x ) = 3 x 2 , ϕ′( −2) = 12 > 1 , ϕ′( −1) = 3 > 1 . Поэтому воспользуемсядругим преобразованием.В результате получим x = 3 x − 1 . Можно проверить, что ϕ′( x ) < 1 на отрезке[− 2; − 1] , т.е.

достаточные условия сходимости выполняются.2. Зададим начальное приближение x (0 ) = −1 . Решим задачу с различной точностью ε1 и ε 2 .3,4. Выполним расчеты по формуле:x (k +1) =3x (k ) − 1 , k = 0,1, 2,...Результаты расчетов приведены в табл. 1.Таблица 1kx (k )x (k ) − x (k −1)0-1,000-12345-1,2599-1,3123-1,3223-1,3243-1,32460,25990,05240,01000,00200,0003Если ε1 = 0,01 , то x ∗ ≅ −1,3223 , а если ε 2 = 0,001 , то x ∗ ≅ −1,3246 .„Пример 2. Найти корни уравнения x 3 − x 2 − 9 x + 9 = 0 методом простых итераций с точностью ε = 0,001 .† I. Отделить корни уравнения x 3 − x 2 − 9 x + 9 = 0 . Уравнение имеет три корня,среди которых по крайней мере один действительный.Преобразуем уравнение к равносильному виду: x 3 = x 2 + 9 x − 9 . Найдем абсциссы точек пересечения графиков y = x 3 и y = x 2 + 9 x − 9 (на рис.

2 указаны два из трехполученных промежутков).Результат отделения корней – три промежутка[0,5; 2] , [2; 4] , [− 4; − 2] .Заметим, что отрезки могут быть сужены, например, вместо отрезка [2; 4] можно принять[2,5; 4] .233y−4y = x3−2024xy = x 2 + 9x − 9Рис. 3II. Преобразуем уравнение к виду x = ϕ( x ) : x = 3 x 2 + 9 x − 9 .Можно показать, что на отрезках [2; 4] , [− 4; − 2] функция ϕ( x ) = 3 x 2 + 9 x − 9удовлетворяет условию ϕ′( x ) < 1 . На отрезке [0,5; 2] используем другой вид уравнения:x3 x2x3 x2x =−+ 1 . Также легко проверить, что функция ϕ( x ) =−+ 1 удовлетворяет9999достаточному условию сходимости на отрезке [0,5; 2] .2. В качестве начальных приближений выберем:– точку x (0 ) = −2 на отрезке [− 4; − 2] ;– точку x (0 ) = 0,5 на отрезке [0,5; 2] ;– точку x (0) = 2 на отрезке [2; 4] .В поставленной задаче ε = 0,001 .3,4.

Выполним расчеты по формуле( )x (k +1) = 3 x (k )2+ 9 x (k ) − 9 , k = 0,1,2,... ,с начальными значениями x ( 0 ) = −2 и x (0) = 2 и по формуле( )3 − (x (k ) )2 + 1 , k = 0,1,2,... ,x (k )x (k +1) =99234с начальным значением x (0 ) = 0,5 . Результаты расчетов занесены в табл. 2-4.Таблица 2kx (k )Таблица 3x (k ) − x (k −1)02,0000-12,35130,351322,60560,254332,76940,163842,86820,098852,92550,057362,95820,032772,97670,018582,98700,010292,99270,0057102,99590,0032112,99770,0018122,99870,0010kx012345-2,0000-2,8438-2,9816-2,9979-2,9997-2,99997(k )x(k )− x (k −1)0,84380,13780,01630,00180,00027Таблица 4k01234x (k )0,500000,986110,998490,999830,99998x (k ) − x (k −1)0,48610,012380,001340,00015В результате получены приближенные значения корней: x1∗ ≅ −2,99997 ,x 2 ∗ ≅ 0,99998 , x 3 ∗ ≅ 2,9987 .Обратим внимание на сильное различие в числе итераций, потребовавшихся длянахождения корней x ∗ = 3 (табл.

2) и x ∗ = −3 (табл. 3), с помощьюодной и той жемодуля производнойформулы. Заметим, что в окрестности корня x ∗ = 3 значенияфункцииϕ( x ) = 3 x 2 + 9 x − 9равны:ϕ′(2) = 0,784 ;ϕ′(2,3513) = 0,673 ;ϕ′(2,6056) = 0,618 ; ϕ′(2,9977) = 0,556 . С другой стороны, в окрестности корня x ∗ = −3имеем: ϕ′(−2) = 0,206 ; ϕ′(−2,8438) = 0,124 ; ϕ′(−2,9977) = 0,111 . Анализ результатовпоказывает, что чем меньше значения модуля производной ϕ′(x ) , тем быстрее сходимость.

„235Б. МЕТОД НЬЮТОНАМетод Ньютона (метод касательных) является одним из наиболее популярныхчисленных методов. Он реализуется по формуле:x ( k +1) = x (k ) −f ( x (k ) )f ′( x ( k ) ), k = 0,1, 2,...yBf ( x (0 ) )y = f (x )a0Cx∗αAx ( 2)x (1)bx (0 )xРис. 4В точке x (0) строится касательная к графику функции. Следующей точкой x (1) является точка пересечения касательной с осью абсцисс. Далее процесс продолжается аналогично.Теорема (о достаточных условиях сходимости метода Ньютона).Пусть выполняются следующие условия:1.

Функция f (x ) определена и дважды дифференцируема на [a, b ] .2. Отрезкуf (a ) ⋅ f (b ) < 0 .[a, b ]принадлежит только один простой корень x ∗ , так что3. Производные f ′( x ), f ′′( x ) на [a, b ] сохраняют знак, и f ′( x ) ≠ 0 .4. Начальное приближение x ( 0 ) удовлетворяет неравенствуf ( x (0) ) ⋅ f ′′( x (0) ) > 0 (знаки функций f (x ) и f ′′(x ) в точке x ( 0 ) совпадают).Тогда с помощью метода Ньютона можно вычислить корень уравнения f ( x ) = 0с любой точностью.236Методика решения задачиШаг 1. Задать начальное приближение x (0) так, чтобы выполнялось неравенствоf ( x (0) ) ⋅ f ′′( x (0) ) > 0 , а также малое положительное число ε .

Положить k = 0 .Шаг 2. Вычислить x (k +1) по формулеx(k +1)=x(k )−f ( x (k ) )f ′( x (k ) ).Шаг 3. Если x (k +1) − x (k ) ≤ ε , процесс завершить и положить x ∗ ≅ x (k +1) .Если x (k +1) − x (k ) > ε , положить k = k + 1 и перейти к п.2.Пример 3. Методом Ньютона найти корень уравнения x 3 − x + 1 = 0 .† В примере 1 корень был отделен: x ∗ ∈ [− 2; − 1].1. Зададим начальное приближение x ( 0 ) . Так как f ′( x ) = 3x 2 − 1 , f ′′( x ) = 6 x , тоf ( −2) = −5 , f ′′( x ) < 0 при x ∈ [− 2; − 1] . Поэтому f (−2) f ′′(−2) > 0 и x ( 0 ) = −2 . Положим ε = 0,001 .2,3.

Результаты расчетов по формуле:x(k +1)=x(k )(x ) − x + 1 , k = 0,1,... ,−3(x ) − 1(k ) 3(k )(k ) 2приведены в табл. 5.Таблица 50kx (k )x (k ) − x (k −1)-2,0000-12345-1,545455-1,359615-1,325801-1,324719-1,3247180,4545450,1858400,0338140,0010820,000001Найденное приближенное решение x ∗ ≅ −1,3247 2. „Пример 4. Найти корни уравненияx 3 − x 2 − 9x + 9 = 0методом Ньютона с точностью ε = 0,001 .† Процедура отделения корней была выполнена в примере 2. В качестве отрезков[ai , bi ] , которым принадлежат корни уравнения, выберем [− 4; − 2] , [2,5; 4] , [0,5; 2] .f (− 4) = −3,5 ;f ( −2) = 15 , т.е.f (− 4) f (−2) < 0 , производныеТак какf ′′( x ) = 6 x − 2 < 0 , f ′( x ) = 3 x 2 − 2 x − 9 > 0 сохраняют знак при x ∈ [− 4; − 2] , то условия сходимости выполняются.237Так как f (2,5) = − 4,125 ; f (4) = 21 , т.е. f (2,5) f (4) < 0 , и производные f ′( x ) > 0 ,f ′′( x ) > 0 сохраняют знак при x ∈ [2,5; 4] , то условия сходимости на этом отрезке тожевыполняются.Так как f (0,5) = 4,375 ; f (2) = −5 , т.е.