semopt11 (1013539)
Текст из файла
Занятие 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 , т.е.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.