Компьютерные методы решения типовых задач математики

Конспект лекций по дисциплине «Численные методы» Составитель: Климова В.А., кафедра «Информационные системы и технологии», УрФУ Оглавление Конспект лекций по дисциплине «Численные методы» 1 Введение 3 1. Методы решения систем линейных алгебраических уравнений 4 Метод Гаусса 5 Метод Крамера 7 Матричный метод (через обратную матрицу) 7 Итерационные методы решения СЛАУ 9 Метод Якоби (простой итерации) 10 Метод Зейделя 12 2. Приближенное решение нелинейных алгебраических уравнений 13 Постановка задачи 13 Метод деления отрезка пополам (дихотомии, бисекции) 15 Метод простой итерации 16 Метод Ньютона (метод касательных) 18 Метод хорд 19 3. Аппроксимация функций 21 Интерполяция 21 Локальная кусочно-постоянная интерполяция 21 Локальная кусочно-линейная интерполяция 22 Кубический интерполяционный сплайн 23 Глобальная интерполяция 25 Полином Лагранжа 26 Сглаживание функции. Метод наименьших квадратов 28 4. Численное интегрирование 30 Постановка задачи: 30 Формулы прямоугольников 31 Формула трапеций 33 Формула Симпсона 34 Пример приближенного вычисления определенного интеграла 35 5. Численное решение обыкновенных дифференциальных уравнений 36 Постановка задачи 36 Метод Эйлера 37 Модифицированный метод Эйлера 39 Метод Рунге – Кутты 39 Численное решение ОДУ первого порядка 39 Численные методы решения систем ОДУ первого порядка 40 Численные методы решения ОДУ высших порядков 41 Метод конечных разностей решения краевых задач для ОДУ 43 Введение В курсе лекций Численные методырассматриваются компьютерные методы решения типовых задач математики, которые наиболее часто встречаются на практике. К ним относятся: • приближение функций, • вычисление определенных интегралов, • решение систем линейных алгебраических уравнений, • решение систем нелинейных алгебраических уравнений, • решение систем обыкновенных дифференциальных уравнений, • методы решения задач математической физики. Численные методы по своей сути являются приближенными, поэтому при использовании численных методов нужно оценивать точность полученного результата, а также устойчивость метода к возникающим на операциях ошибкам. Характеристики численных методов Устойчивость – свойство метода, при котором ошибка, допущенная на i-м шаге процесса, на следующем шаге не увеличивается, если операция сложения выполнена без новых ошибок. Точность – оценка погрешности приближенного значения. Выделяют: • методическую погрешность модели – погрешность, которую вносит переход от реального явления к математической модели; • алгоритмическую погрешность; • трансформируемую погрешность, связанную с ошибкой исходных данных; • вычислительную погрешность, обусловленную точностью арифметических операции в ЭВМ (ошибка округления). Абсолютной погрешностью называют оценку Δ, такую что Δ = |F – f|, где F – действительное значение некой величины, а f – ее вычисленное значение. Относительной погрешностью называют величину δ = Δ/|F|. Вычисление величины должно производиться с некоторой заданной точностью ε, следовательно, критерием завершения уточнения решения будет Δ ≤ ε. На практике получить абсолютную погрешность невозможно, т.к. действительное значение не известно, поэтому вместо абсолютной погрешности используют ее оценку сверху – предельную абсолютную погрешность Δf > Δ. Если решением задачи является вектор v, то для оценки ошибки решения используется количественная характеристика вектора – норма ||v||. Норма вектора – это вещественное число, для которого справедливо: 1. ||v|| ≥ 0, причем ||v|| = 0 только в случае v = 0; 2. ||a·v|| = |a|·||v|| для любого вектора v и любого числа a; 3. ||z + v|| ≤ ||z|| + ||v|| для любых векторов v и z. В вычислительных методах используют следующие нормы вектора: Для матрицы решений А используется норма матрицы ||A||, для которой справедливы свойства, аналогичные свойствам нормы вектора. Норма матрицы вычисляется по правилам: где j(ATA) – собственные числа матрицы АТА. Эффективность – величина, характеризующая время реализации либо общее число операций, необходимых для получения результата. Экономичность алгоритма оценивается по требуемым для его реализации объемам памяти ЭВМ. Аварийные остановы. При использовании ЭВМ необходимо строить вычислительный алгоритм так, чтобы вычисленные в процессе его работы числа не выходили за интервалы, принятые для данного класса чисел, потому что это приводит к аварийным остановам. 1. Методы решения систем линейных алгебраических уравнений Многие задачи математической физики сводятся к численному решению систем линейных алгебраических уравнений (СЛАУ). Постановка задачи Системой линейных алгебраических уравнений называется система вида где m – количество уравнений; n – количество неизвестных; x1…xn – неизвестные, которые нужно определить; a11…amn – коэффициенты системы; b1…bm – свободные члены. Индексы коэффициента aij обозначают номер уравнения и неизвестного, при котором стоит этот коэффициент. Представление СЛАУ в матричной форме: или A∙x = b. Требуется найти решение системы. Необходимым и достаточным условием существования единственного решения СЛАУ является условие det A ≠ 0, т.е. определитель матрицы A не равен нулю. В случае равенства нулю определителя матрица A называется вырожденной и при этом СЛАУ либо не имеет решения, либо имеет их бесчисленное множество. Методы решения СЛАУ Прямые (точные) методы – дают точное решение системы, т.е. погрешность алгоритма равна 0: • Метод Крамера; • Метод обратной матрицы; • Метод Гаусса; • Алгоритм Томаса (метод прогонки); • Разложение Холецкого и т.д. Итерационные методы – дают решение с некоторой погрешностью: • Метод простой итерации (метод Якоби); • Метод Зейделя • Метод релаксации и т.д. Метод Гаусса Это классический метод решения СЛАУ путем последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные. Элементарные преобразования – это: • перестановка местами любых двух строк матрицы; • умножение любой строки матрицы на константу α≠0; • прибавление к любой строке матрицы другой строки. В результате элементарных преобразований сохраняется эквивалентность системы. Методика Пусть имеется система вида A∙x = b. Решение ищется в два этапа, которые называются прямым и обратным ходом. Перед применением метода Гаусса нужно преобразовать матрицу А так, чтобы на главной диагонали не было нулей (выбор главного элемента). 1. Прямой ход. Путем элементарных преобразований над строками приводим основную матрицу к ступенчатому (треугольному) виду (эти же преобразования нужно применять к столбцу свободных членов). В результате в матрице коэффициентов под главной диагональю только 0: Это делается так: вычитаем первую строку из остальных строк, домножив её на отношение первого элемента каждой из этих строк к первому элементу первой строки. Это позволит обнулить столбец под первым элементом. Затем первую строку и первый столбец мысленно вычёркиваем, над оставшимися выполняем те же действия, пока не останется матрица нулевого размера. 2. Обратный ход. Вычисляем неизвестные из уравнений системы, начиная с последнего. В последнем уравнении всего одна неизвестная. Ее подставляют в предыдущее уравнение, и так далее, поднимаясь по «ступенькам» наверх. В каждой строчке таким образом оказывается только одна неизвестная переменная. Пример. Решение СЛАУ по методу Гаусса. 1. Приведем систему к треугольному виду: Обнулим коэффициенты при х во 2 и 3 строчках (вычитаем первую строчку, умноженную на 3/2 и 2/2, соответственно): Обнулим коэффициент при y в 3-й строке (вычтем из нее 2-ю, умноженную на 4): 2. Разрешим полученные уравнения в обратном порядке: z = -1; y = 3; x = 2. Метод Крамера Метод назван по имени Габриэля Крамера (1704-1752), придумавшего его. Применяется для квадратных матриц с ненулевым определителем. Решение ищется в виде xi = Δi/Δ, где Δi – определитель матрицы, получаемой из А заменой i-го столбца на столбец b, Δ – определитель исходной матрицы А. Пример. Решение СЛАУ по правилу Крамера. Определители: Матричный метод (через обратную матрицу) Если det A ≠ 0, то существует обратная матрица А-1. Тогда решение СЛАУ записывается в виде: x = A-1·b. Следовательно, решение СЛАУ свелось к умножению известной обратной матрицы на вектор правых частей. Таким образом, задача решения СЛАУ и задача нахождения обратной матрицы связаны между собой, поэтому часто решение СЛАУ называют задачей обращения матрицы. Проблемы использования этого метода те же, что и при использовании метода Крамера: нахождение обратной матрицы – трудоемкая операция. Пример. Решение СЛАУ матричным методом. Определитель матрицы из коэффициентов при неизвестных СЛАУ det A = -103. Теперь вычислим алгебраические дополнения для элементов матрицы, состоящей из коэффициентов при неизвестных. Они нам понадобятся для нахождения обратной матрицы. Далее найдём союзную матрицу, транспонируем её и подставим в формулу для нахождения обратной матрицы. Подставляя переменные в формулу, получаем: Осталось найти неизвестные. Для этого перемножим обратную матрицу и столбец свободных членов. Итак, x=2; y=1; z=4. Итерационные методы решения СЛАУ Итерационные методы основаны на использовании повторяющегося процесса и позволяют получить решение в результате последовательных приближений. Естественно, даже при отсутствии ошибок округления с помощью этих методов невозможно найти точное решение при условии конечного числа итераций. Поэтому говорят о решении СЛАУ с заданной точностью. Итерационные методы устанавливают процедуру уточнения определённого начального приближения к решению. При выполнении условий сходимости они позволяют достичь любой заданной точности просто повторением итераций. Преимущество этих методов в том, что часто они позволяют достичь решения с заранее заданной точностью быстрее, чем прямые методы, а также позволяют решать большие системы уравнений. Первым шагом в итерационном методе является преобразование исходной системы (Ах = b) к виду A1х = A2х + b1. Здесь матрицы A1, A2 и вектор b1 определяются по матрице A и вектору b. Системы эквивалентные, то есть их решения совпадают. Вторым шагом является расстановка индексов или номеров приближений в формуле и задание нулевого приближения. Например, A1х(k+1) = A2х(k) + b1, k = 0, 1, 2, …, где x(0) - заданный вектор (нулевое приближение). Третьим шагом итерационного метода является обоснование сходимости последовательных приближений {x(k)} к точному решению x системы и оценка погрешности k-го приближения ||x(k) – x|| < ε. Оценка такого типа при заданном ε (точность решения) позволяет закончить итерационный процесс. Здесь также предполагается, что система решается относительно x(k+1) гораздо легче, чем исходная система относительно x. Разные итерационные методы различаются первыми двумя шагами, а выбор конкретного метода производится на основании оценки сходимости. Метод Якоби (простой итерации) Итак, требуется решить систему линейных уравнений, которая в матричном виде записывается как A∙x = b. Разрешим первое уравнение системы относительно x0, второе относительно x1 и т.д. Получим следующую эквивалентную систему, записанную в скалярном виде: x0 = 1/a0,0 · (b0 – (a0,1x1+a0,2x2+…+a0,nxn)); x1 = 1/a1,1 · (b1 – (a1,0x0+a1,2x2+…+a1,nxn)); … xn = 1/an,n · (bn – (an,0x0+an,1x1+…+an,n-1xn-1)). Теперь, задав нулевое приближение xi(0), по этим соотношениям можно выполнять итерационный процесс, а именно: 1-я итерация: x0(1) = 1/a0,0 · (b0 – (a0,1x1(0)+a0,2x2(0)+…+a0,nxn(0))) и т.д.; 2-я итерация: x0(2) = 1/a0,0 · (b0 – (a0,1x1(1)+a0,2x2(1)+…+a0,nxn(1))) и т.д. Или в общем случае: xi(k) = 1/ai,i · (bi – (ai,0x0(k-1)+…+ai,i-1xi-1(k-1)+ai,i+1xi+1(k-1)+…+ai,nxn(k-1))) Условие окончания итерационного процесса max|xi(k+1)-xi(k)|≤ε. Условия сходимости Достаточное условие: Если выполнено условие диагонального преобладания, т.е. , то итерационный процесс сходится при любом выборе начального приближения. Если исходная система уравнений не удовлетворяет условию сходимости, то ее приводят к виду с диагональным преобладанием путем элементарных преобразований. Указанное выше условие сходимости является достаточным, т.е. если оно выполняется, то процесс сходится. Однако процесс может сходиться и при отсутствии диагонального преобладания, а может и не сойтись. Выбор начального приближения влияет на количество итераций, необходимых для получения приближенного решения. Наиболее часто в качестве начального приближения берут xi(0)=0 или xi(0)=bi/aii. Пример. Решение СЛАУ методом Якоби. Решим систему линейных уравнений с точностью ε = 0,01. В матричном виде 8 4 2 10 x1 А= 3 5 1 b= 5 x= x2 3 -2 10 4 x3 Решение прямыми методами х1 = 1,038; х2 = 0,346; х3 = 0,158. Найдем решение методом простой итерации. Проверяем условие диагонального преобладания: |8| > |4|+|2|; |5| > |3|+|1|; |10| > |-2|+|3|. Выражаем неизвестные переменные: Примем начальное приближение xi(0)=0. Дальнейшие вычисления оформим в виде таблицы. Точность вычисляется как max|xi(k+1)-xi(k)|. № итерации k x1 x2 x3 точность 1 1,2500 1,0000 0,4000 1,25 2 0,6500 0,1700 0,2250 0,83 3 1,1088 0,5650 0,2390 0,45875 4 0,9078 0,2870 0,1804 0,27805 5 1,0614 0,4193 0,1851 0,153681 6 0,9941 0,3261 0,1654 0,093147 7 1,0456 0,3705 0,1670 0,051483 8 1,0230 0,3393 0,1604 0,031204 9 1,0403 0,3541 0,1609 0,017247 10 1,0327 0,3436 0,1587 0,010453 11 1,0385 0,3486 0,1589 0,005778 Таким образом, приближенное решение имеет вид х1 = 1,038; х2 = 0,349; х3 = 0,159 и найдено с заданной точностью на 11-й итерации. Метод Зейделя Метод Зейделя основан на идее, что, если подставлять в уравнения для i-й неизвестной переменной уже вычисленные на этой итерации значения i-1 компонент, то заданная точность будет достигнута быстрее. В уравнения для xi(k+1) подставляются xj(k+1), если ji. Расчетные формулы имеют вид x0(k+1) = 1/a0,0 · (b0 – (a0,1x1(k)+a0,2x2(k)+…+a0,nxn(k))); x1(k+1) = 1/a1,1 · (b1 – (a1,0x0(k+1)+a1,2x2(k)+…+a1,nxn(k))); … xi(k+1) = 1/ai,i · (bi – (ai,0x0(k+1)+…+ai,i-1xi-1(k+1)+ai,i+1xi+1(k)+…+ai,nxn(k))) … xn(k+1) = 1/an,n · (bn – (an,0x0(k+1)+an,1x1(k+1)+…+an,n-1xn-1(k+1))). Достаточное условие сходимости этого метода такое же, как и для метода простой итерации, т,е, диагональное преобладание. Пример. Решение СЛАУ методом Зейделя Найдем решение системы из предыдущего примера методом Зейделя. . Расчетные формулы: Результат № итерации k x1 x2 x3 точность 1 1,2500 0,2500 0,0750 1,25 2 1,1063 0,3213 0,1324 0,14375 3 1,0563 0,3398 0,1511 0,049969 4 1,0424 0,3444 0,1562 0,013926 5 1,0388 0,3455 0,1575 0,003584 Приближенное решение имеет вид х1 = 1,039; х2 = 0,346; х3 = 0,158 и найдено с заданной точностью на 5-й итерации. 2. Приближенное решение нелинейных алгебраических уравнений Постановка задачи Дано нелинейное алгебраическое уравнение f(x) = 0. Нелинейность уравнения означает, что график функции не есть прямая линия, т,е, в f(x) входит x в некоторой степени или под знаком функции. Решить уравнение – это найти такое x* ∈ R: f(x*) = 0, Значение x* называют корнем уравнения. Нелинейное уравнение может иметь несколько корней. Геометрическая интерпретация корней уравнения представлена на рисунке. Корнями уравнения здесь являются точки x1*, x2*, x3*, в которых функция f(x) пересекает ось x. Методы решения нелинейного уравнения можно разделить на точные (аналитические) и приближенные (итерационные). В точных методах корень представляется некоторой алгебраической формулой. В приближенных методах процесс нахождения решения, вообще говоря, бесконечен. Решение получается в виде бесконечной последовательности {xn}, такой, что . Члены этой последовательности xn называются последовательными приближениями к решению, или итерациями. Заданное число ε называют точностью метода, а n – это количество итераций, которое необходимо выполнить, чтобы получить решение с точностью ε. Существует различные методы нахождения приближенного решения, т,е, способы построения последовательности итераций {xn}, однако все они имеют общие этапы, изображенные на рисунке. Наиболее часто используется следующий критерий остановки итерационного процесса: |xn+1–xn|<ε, т.е. разница между соседними итерациями становится малой. Интервалы изоляции корней Прежде чем использовать приближенный метод, уравнение надо исследовать на наличие корней и уточнить, где эти корни находятся, т.е. найти интервалы изоляции корней. Интервалом изоляции корня называется отрезок, на котором корень уравнения существует и единственен. Необходимое условие существования корня уравнения на отрезке [a,b]: Пусть f(x) непрерывна и f(a)·f(b)<0 (т.е. на концах интервала функция имеет разные знаки). Тогда внутри отрезка [a, b] существует хотя бы один корень уравнения f(x)=0. Достаточное условие единственности корня на отрезке [a,b]: Корень будет единственным, если f(a)·f(b)<0 и производная f '(x) не меняет знак на отрезке [a, b], т.е. f(x) – монотонная функция, в этом случае отрезок [a, b] будет интервалом изоляции. Если корней несколько, то интервал изоляции нужно найти для каждого. Способы определения интервалов изоляции: Аналитический способ состоит в нахождении экстремумов функции f(x), исследование ее поведения при х→±∞ и нахождение участков возрастания и убывания функции. Графический способ – это построение графика функции f(x) и определение числа корней по количеству пересечений графика с осью x. Табличный способ – это построение таблицы, состоящей из столбца аргумента x и столбца значений функции f(x). О наличии корней свидетельствуют перемены знака функции. Чтобы не произошла потеря корней, шаг изменения аргумента должен быть достаточно мелким, а интервал изменения достаточно широким. Пример. Решить уравнение x3‑6x2+3x+11=0, т.е. найти корни f(x)= x3‑ 6x2+3x+11. Аналитический способ: Найдем производную f’(x)=3x2-12x+3. Найдем нули производной: D=144-4·3·3=108; x1=(12-√D)/(2·3)=0,268; x2=(12+√D)/(2·3)=3,732. Так как f’(-∞)>0, то f’(x)>0 при x∈(-∞,x1); f’(x)<0 при x∈(x1,x2) и f’(x)>0 при x∈(x2,+∞). Кроме того, f(-∞)=-∞<0, f(+∞)=+∞>0. Следовательно, функция на интервале [-∞,x1] возрастает от -∞ до f(x1)=11,39; на интервале [x1,x2] убывает и на интервале [x2,+∞] возрастает от f(x2)=-9,3 до +∞, т.е. уравнение имеет три корня. Найдем интервалы изоляции для каждого из корней. Рассмотрим для первого корня отрезок [-2, -1]: f(-2)= -27<0, f(-1)= 1>0, f’(x)>0, т.е. этот отрезок является интервалом изоляции корня. Рассмотрим для второго корня отрезок [1, 3]: f(1)=9>0, f(3)=-7<0, f’(x)<0, т.е. этот отрезок является интервалом изоляции корня. Рассмотрим для третьего корня отрезок [4, 5]: f(4)=-9<0, f(5)=1>0, f’(x)>0, т.е. этот отрезок является интервалом изоляции корня. Табличный способ: x -3 -2 -1 1 2 3 4 5 6 7 f(x) -79 -27 1 11 9 1 -7 -9 1 29 81 Графический способ Метод деления отрезка пополам (дихотомии, бисекции) Идея метода: Найдем середину отрезка [a, b]: c=(a+b)/2. Корень остался на одной из частей: [a, c] или [c, b]. Если f(a)·f(с)<0, то корень попал на отрезок [a, c], тогда деление отрезка можно повторить, приняв в качестве нового правого конца точку c, т,е, b=c. В противном случае корень попал на половину [c, b], и необходимо изменить значение левого конца отрезка: a=c. Поскольку корень всегда заключен внутри отрезка, итерационный процесс можно останавливать, если длина отрезка станет меньше заданной точности: |b–a|<ε. Пример. Решение уравнения методом деления отрезка пополам Найдем первый корень уравнения f(x)=x3-6x2+3x+11=0 с точностью ε=0,05. № итерации a b c f(a) f(c) |b-a| -2 -1 -1,5 -27 -10,375 1 1 -1,5 -1 -1,25 -10,375 -4,0781 0,5 2 -1,25 -1 -1,125 -4,0781 -1,3926 0,25 3 -1,125 -1 -1,0625 -1,3926 -0,1604 0,125 4 -1,0625 -1 -1,0313 -0,1604 0,4287 0,0625 5 -1,0625 -1,0313 -1,0469 -0,1604 0,1364 0,03125 6 -1,0625 -1,0469 -1,0547 -0,1604 -0,01146 0,01563 Здесь a0, b0 – начальные границы интервала изоляции корня, сi=(ai+bi)/2, В результате расчета приближенное значение первого корня: x=-1,0469 при ε=0,05. Графическая иллюстрация метода: Метод простой итерации С помощью эквивалентных преобразований приведем исходное уравнение f(x) к виду, удобному для применения метода простой итерации: x=φ(x). Выберем начальное приближение x0∈[a, b]. Следующие итерации находим по формуле: xk+1=φ(xk), т.е. x1=φ(x0), x2=φ(x1) и т.д. Итерационный процесс заканчивается, если |xk+1–xk|<ε. Представить исходное уравнение в эквивалентном виде x=φ(x) можно бесконечным числом способов. Из всевозможных таких представлений выбирают тот, который дает сходящуюся к корню последовательность вычислений. Достаточное условие сходимости. Пусть φ(x) имеет производную на отрезке [a, b], φ(x)∈[a, b] и |φ’(x)|<1 для всех x из отрезка [a, b], тогда итерационный процесс сходится к корню уравнения т.е. . Геометрический смысл метода простой итерации Сходящийся метод простой итерации. 0<φ’<1 -1<φ’<0 Расходящийся метод простой итерации φ’>1 φ’<-1 В качестве начального приближения обычно берут середину отрезка [a, b]: x0=(a+b)/2. В качестве φ(х) на практике часто берут функцию φ(х)=x - сf(x), где с – некоторая постоянная. Постоянную c выбирают таким образом, чтобы |φ’(x)|≤q<1 всех x из отрезка [a, b]. При таком выборе функции φ(х) метод простой итерации называют методом релаксации. Получим условия на выбор с: |φ’(x)|=|1 – cf’(x)|<1, следовательно -1<1 – cf’(x)<1, следовательно -2<– cf’(x)<0. Таким образом, если f’(x)<0, то 2/f’(x)0, то 2/f’(x)>c>0. Видно, что знак с совпадает со знаком f’(x). Часто с берут в виде: c=2/(M+m), где M=max(f’(x)), m=min(f’(x)). Пример. Вычисление корня методом простой итерации. Найдем второй корень нашего исходного уравнения x3‑ 6x2+3x+11=0, который лежит на интервале [1, 3] с точностью ε=0,05. Сначала найдем функцию φ(х). В нашем случае f(x)= x3‑ 6x2+3x+11. Для нахождения c необходимо найти максимальное и минимальное значения f’(x) на отрезке [1, 3]. Для этого найдем значения f’(x) на концах интервала и в точках, где f”(x)=0, т.е. в точках экстремума, если такие точки для рассматриваемого интервала существуют. И выбрать среди этих значений f’(x) максимальное и минимальное значения. f’(1)=3x2-12x+3=-6, f’(3)=-6, f”(x)=6x-12=0 при x=2, f’(2)=-8. Следовательно, M=-6; m=-8, c=2/(M+m)=-1/7. Тогда функция φ(х)=х+1/7·(х3-6х2+3х+11). Результаты вычислений по формуле xk+1=φ(xk). k x |xk+1-xk| |f(xk)| 2 - 1 1 2,142857 0,142857 0,282799 2 2,102457 0,0404 0,07896 3 2,113737 0,01128 0,022164 Метод Ньютона (метод касательных) Метод определяется формулой Геометрическая интерпретация Участок кривой y=f(x) при х от хk до xk+1 заменяется отрезком касательной, проведённой из точки xk. Уравнение касательной имеет вид y=f(xk)+(x-xk)f’(xk). Найдем точку пересечения, которую обозначим xk+1, касательной с осью y=0: 0= f(xk)+(xk+1-xk)f’(xk), откуда Можно показать, что |xk+1–x*| < q·|xk–x*|2, т.е. метод сходится со вторым порядком. Метод Ньютона можно трактовать как метод простой итерации при φ(х)=x-f(x)/f’(x). Примечание: Если известен интервал изоляции корня уравнения, в котором f"(x) не меняет знак, то в качестве начального приближения берут тот конец интервала изоляции, для которого знаки f(x) и f"(x) совпадают. Пример. Решение уравнения методом Ньютона. Найдем методом Ньютона третий корень нашего исходного уравнения x3‑6x2+3x+11=0, который лежит на интервале [4, 5] с точностью ε=0,001. Сначала убедимся, что f"(x) не меняет знака на этом отрезке: f"(x)=6x-12, f"(x)>0 при x>2, т.е. f"(x)>0 на интервале [4, 5]. Так как f(5)=1>0, то x0=5. k xk |xk+1-xk| f(xk) f'(xk) 5 1 18 1 4,944444 0,05556 0,02760 17,0092 2 4,942821 0,00162 2,33·10-5 16,98059 3 4,942820 1,37·10-6 1,66·10-11 16,98057 Здесь f(xk)=xk3‑ 6xk2+3xk+11, f/(xk)=3xk-12xk+3, xk+1=xk-f(xk)/f’(xk). Видно, что процесс сошелся уже на третьей итерации. Метод Ньютона является более быстросходящимся. Но для его использования необходимо брать начальное приближение достаточно близким к корню. Метод хорд В этом методе кривая f(x) заменяется прямой линией – хордой, стягивающей точки (a, f(a)) и (b, f(b)). В зависимости от знака выражения f(a)·f"(a) метод хорд имеет два варианта, изображенных на рисунке. f(a)·f"(a)>0 f(a)·f"(a)<0 Пусть f(a)·f"(a)>0. Тогда x0=b, точка a будет оставаться неподвижной. Следующее приближение x1 находим как точку пересечения хорды, соединяющей точки (a, f(a)) и (x0, f(x0)) с осью x. Уравнение хорды: Тогда точка пересечения хорды с осью x: Для случая f(a)·f"(a)<0 На следующей итерации в качестве x0 надо взять вычисленное значение x1. Таким образом, имеем следующую последовательность вычислений: x0=b, если f(a)·f"(a)>0; x0=a, если f(a)·f"(a)<0. Окончание итерационного цикла в этом методе происходит по условию малости невязки уравнения: |f(xk+1)|<ε или |xk+1-xk|<ε. Пример. Нахождение корней методом хорд. Найдем первый корень уравнения x3‑6x2+3x+11=0 методом хорд с точностью ε=0,01 (по |xk+1-xk|). Для первого корня a=-2, b=-1, f”(-2)·f(-2)=(-24)·(-27)>0, следовательно, расчет ведется по первым формулам: x0=b и k xk |xk+1-xk| f(xk) -1 1 1 -1,0357 0,03571 0,34562 2 -1,0479 0,01219 0,11701 3 -1,0520 0,00411 0,03933 4 -1,0534 0,00138 0,01319 3. Аппроксимация функций Аппроксимировать – это означает «приближённо заменять». Применение: а) Допустим, известны значения некоторой функции в заданных точках. Требуется найти промежуточные значения этой функции. Это так называемая задача о восстановлении функции. б) При проведении расчетов сложные функции удобно заменять алгебраическими многочленами или другими элементарными функциями, которые достаточно просто вычисляются (задача о приближении функции). Интерполяция Постановка задачи На интервале [a, b] заданы точки xi, i=0, 1, … n; a ≤ xi ≤ b, и значения неизвестной функции в этих точках fi, i=0, 1, … n. Требуется найти функцию F(x), принимающую в точках xi те же значения fi. При этом F(x) ищем только на отрезке [a, b]. Точки xi называются узлами интерполяции, а условия F(xi)=fi, – условиями интерполяции. Будучи представлены в виде таблицы, xi и соответствующие fi носят название узловой таблицы. Если необходимо найти функцию вне отрезка, то это – задача экстраполяции. Задача интерполяции имеет много решений, т.к. через заданные точки (xi, fi), i=0, 1, … n, можно провести бесконечно много кривых, каждая из которых будет графиком функции, для которой выполнены все условия интерполяции. Для практики важен случай аппроксимации функции многочленами (полиномами), т.е. F(x)=a0+a1x+a2x2+…+amxm. Все методы интерполяции можно разделить на локальные и глобальные. В случае локальной интерполяции на каждом интервале [xi–1, xi] строится отдельный полином. В случае глобальной интерполяции отыскивается единый полином на всем интервале [a, b]. При этом искомый полином называется интерполяционным полиномом. Локальная кусочно-постоянная интерполяция На каждом отрезке [xi-1, xi] интерполяционный многочлен равен константе, а именно левому или правому значению функции. Для левой кусочно-линейной интерполяции F(x)=fi-1, если xi-1≤x