Презентация по информатике. Программирование. Приближенные методы решения уравнений. Метод Ньютона.

МЕТОД Ньютона (метод касательных) Кондраткова Т.А.,учитель информатики в.к.к. ГОУ лицея № 82 Петроградского района СПб. 28.11.2011 Численные методы решения уравнений Вопросыдля повторения: В каких случаях мы прибегаем к численным методам решения уравнений? Что значит корень вычислен с заданной степенью точности ε ? Вопросыдля повторения: Из каких этапов состоит процесс нахождения корней приближенными (численными) методами? Что значит отделить корни? Четыре варианта поведения функции на отрезке в окрестности корня ПОСТАНОВКА ЗАДАЧИ: Пусть корень ξ уравнения f(x) =0 отделён на отрезке [a,b], причёмf’(x) и f’’(x) непрерывны и сохраняют знак на всём отрезке.Требуется определить вещественный корень этого уравнения, заключенный на отрезке [a,b] с точностью ε. Геометрический смысл метода Ньютона Геометрический смысл метода Ньютона состоит в том, что дуга кривой Y=f(x) заменяется касательной к этой кривой (отсюда второе название: метод касательных). В качестве приближенного значения к корню берётся точка пересечения касательной с осью абсцисс. Геометрический смысл метода Ньютона Первый случай: Геометрический смысл метода Ньютона Первый случай: Y=f(b)+f’(b)(x-b) илиY-f(b)=f’(b)(x-b) Уравнение касательной функции в точке B0 Подставляем Y=0 и X=X1 X1=b-f(b)/f’(b)X2=X1 –f(X1)/f’(X1) ИТЕРАЦИОННАЯ ФОРМУЛА X1=X0 - f(X0)/f’(X0), где X0=bX2=X1 – f(X1)/f’(X1)… Xn+1=Xn – f(Xn)/f’(Xn) Первый случай ИТЕРАЦИОННАЯ ФОРМУЛА X1=X0 - f(X0)/f’(X0), где X0=аX2=X1 – f(X1)/f’(X1)… Xn+1=Xn – f(Xn)/f’(Xn) Второй случай ПРАВИЛОвыбора начального приближения: При выборе начального приближения корня X0 за исходную точку следует выбрать тот конец отрезка [a,b],в котором знак функции совпадает со знаком второй производной.Условие для проверки в программе:f(b)*f’’(b)>0 или f(a)*f’’(a)>0 Точностьприближения | ξ –Xn|<= |f(Xn)|/m, где m=min|f’(x)| [a,b]|Xn+1-Xn|=|f(Xn)/f’(Xn)|<|f(Xn)|/mСледовательно точность достигнута, если|f(Xn)/f’(Xn)|< ε Замечание 1: В случае, когда отрезок [a,b] настолько мал, что на нём выполняется условие:M2<2*m1, где M2 =max|f’’(x)| [a,b] m1=min|f’(x)| [a,b]Точность приближения оценивается следующим образом:Если |Xn+1-Xn|< ε, то |ξ-Xn|< ε2 Замечание 2: Если производная f’(x) мало изменяется на отрезке [a,b], то для упрощения вычислений можно пользоваться формулойXn+1=Xn-f(Xn)/f’(X0)То есть значение производной надо вычислить только один раз в начальной точке. Геометрически это означает, что касательные в точках Bn(Xn,f(Xn)) заменяются прямыми, параллельными касательной , проведённой к кривой y=f(x) в точке B0(X0,f(X0)) Модифицированный метод Ньютона: Если вычисление производной в методе Ньютона затруднено, то можно заменить её вычисление оценкой: f’(x)≈(f(X+h)-f(x))/h X3-2X2-X+2=0 [-1.5,0.5] E=0.001 Результат:X= -1 ДАННЫЕ ДЛЯ ТЕСТИРОВАНИЯ Описание данных в программе Var x,x1,a,b,e,R:real; Function f(t:real):real; Begin F:=sqr(t)*t-2*sqr(t)-t+2; End; Function f1(t:real):real; Begin F:=3*sqr(t)-4*t-1; End; Function f2(t:real):real; Begin F:=6*t-4; End; Текстовое описание алгоритма метода Ньютона Ввести точность E;Ввести концы отрезка [a,b], сделать проверку существования корня на этом отрезке;Выбрать начальное приближение:Если f(a)*f2(a)>0, то X=a, иначе X=b;Вычислить R:=f(X)/f1(X);Вычислить X1:=X-R;Сделать проверку точности:Если abs(R)>E, то X:=X1 и повторить с пункта 4., иначе конец цикла;Печать приближенного значения корня X1;Конец программы. Задание на дом: По конспекту выучить основные определения и понятия;Знать итерационную формулу и формулу для оценки точности; Знать геометрический смысл метода Ньютона; Составить блок-схему по текстовому описанию алгоритма метода Ньютона.