Метод Ньютона (касательных).

⇐ ПредыдущаяСтр 4 из 4

Пусть на отрезке [a, b] функция f(x) непрерывна и принимает на концах отрезка значения разных знаков, а производные f ′ (x) и f ″ (x) сохраняют постоянный знак на интервале (a, b).

Геометрический смысл метода касательных состоит в том, что дуга кривой

y = f(x) заменяется касательной к этой кривой.

Рис.7.Иллюстрация метода касательных.

Выберем в качестве начального приближения х₀ = a и проведём в точке А₀(a, f(a)) касательную к графику функции f(x). Абсцисса пересечения касательной с осью Ох (у = 0) является первым приближением к корню (рси.7):

или х₀ = .

Через точку А₁(х₁; f(x₁)) снова проведём касательную, абсцисса точки пересечения которой даст второе приближение х₂ корня ξ и т.д. Очевидно, что в точке А_n(x_n; f(x_n)):

y − f(x_n) = f ′ (x_n)(x− x_n)

и алгоритм метода Ньютона запишется так:

(4)

Заметим, что в нашем случае, если положить х₀ = b и провести касательную к кривой у = f(x) в точке b, то первое приближение не принадлежит отрезку [a, b].

Таким образом, в качестве начального приближения х₀ выбирается тот конец интервала [a, b], для которого знаки f(x) и f ″ (x) одинаковы.

Условие окончания вычислений:

│ с_n₊₁ − c_n│ < ε или │ f(c_n)│ < ε ₁.

Для оценки погрешности можно пользоваться общей формулой

, где

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

Методы хорд и касательных дают приближения корня с разных сторон. Поэтому их часто применяют в сочетании друг с другом, и уточнение корня происходит быстрее.

Пусть дано уравнение f(x)=0, корень ξ отделён и находится на отрезке [a, b]. Применим комбинированный метод хорд и касательных с учётом типа графика функции (рис.4).

Если f (x)· f ″ (x) < 0 (рис.4 в, г), то методом хорд получаем значение корня с избытком, а методом касательных – с недостатком.

Если f (x)· f ″ (x) > 0 (рис.4 а, б), то метод хорд даёт приближение корня с недостатком, а метод касательных – с избытком.

Рассмотрим случай, когда f (b) < 0, f ″ (x) > 0 (рис.8), то со стороны конца а лежат приближённые значения корня, полученные по методу касательных, а со стороны конца b – значения, полученные по методу хорд.

Рис.8Иллюстрация комбинированного метода.

Тогда , .

Теперь истинный корень ξ находится на интервале [a₁, b₁]. Применяя к этому интервалу комбинированный метод, получаем

и вообще

, . (5)

Для случая, когда f (b)· f ″ (x) > 0, то рассуждая аналогично, получим следующие формулы для уточнения корня уравнения:

, . (6)

Комбинированный метод очень удобен при оценке погрешности вычислений. Процесс вычислений прекращается, как только станет выполняться неравенство

‌ ‌ ‌ ‌ ‌ ‌ ‌ |b_n₊₁–a_n₊₁| < ε.

Корень уравнения есть среднее арифметическое последних полученных значений: ξ =(‌ a_n₊₁+b_n₊₁)/2

Лекция 5.

Приближённое решение обыкновенных дифференциальных уравнений и систем обыкновенных дифференциальных уравнений.

Пусть функция у = f(x, y) отражает количественную сторону некоторого явления. Рассматривая это явление, мы можем установить характер зависимости между величинами х и у, а также производными от у по х, т.е. написать дифференциальное уравнение.

Определение: Обыкновенным дифференциальным уравнением называется уравнение, связывающее независимую переменную х, искомую функцию y=f(x) и её производные.

Запись: F( x, y, y′, y′ ′, …, y⁽ⁿ⁾) = 0 или .

Определение: Порядком дифференциального уравнения называется порядок наивысшей производной, входящей в уравнение.

у′ -2ху³+5=0----- уравнение первого порядка,

у″ +ky′ -by-sinx=0------ уравнение второго порядка.

Задача Коши (для уравнения первого порядка):

у′ = f(x, y) (1) найти решение y = y(x),

удовлетворяющее начальному условию: у(х₀)=у₀. (1*).

Т.е. найти интегральную кривую, проходящую через точку М(х₀, у₀).

Если f(x, y) непрерывна в области R: |x-x₀| < a, |y-y₀| < b, то существует по меньшей мере одно решение у = у(х), определённое в некоторой окрестности: |х-х₀| < h, где h ― положительное число. Это решение единственно, если в R выполнено условие Липшица: (2)

Где N― постоянная (константа Липшица), зависящая в общем случае от a и b. Если f(x, y) имеет ограниченную производную в R, то можно положить:

Для дифференциального уравнения n-го порядка: у⁽ⁿ⁾=f(x, y, y′, …, y⁽ⁿ^-1)) задача Коши состоит в нахождении решения у = у(х), удовлетворяющего начальным условиям:

у(х₀) = у₀, у′ (х₀) = у′ ₀, …, у⁽ⁿ^-1)(x₀) = y⁽ⁿ^-1)₀ ― заданные числа.

Функция у = f(x, C₁, C₂, …, C_n), где С₁, …, С_n― произвольные постоянные, называется общим решением ОДУ или общим интегралом.

Эти постоянные можно определить с помощью начальных условий. Решение ДУ при заданных начальных условиях называется его частным решением.

Определение: задача называется краевой, если указывается интервал интегрирования [a, b] и ставятся дополнительные условия для значений функции у и её производных на концах этого интервала.

Процесс познания закономерностей и стремление создать детальную картину исследуемых явлений приводит к более сложной количественной оценке, отражающей эти явления, а именно к функции многих переменных, зависящих как от пространственных координат, так и от времени u = f(x₁, x₂, …, x_n, t).

Определение: Дифференциальным уравнением с частными производными называется уравнение, связывающее независимую переменные х₁, х₂, …, х_n, t, искомую функцию

u = f (х₁, х₂, …, х_n, t) и её частные производные:

Постановка задачи.

Дано дифференциальное уравнение первого порядка: у′ = f(x, y) (1).

Требуется найти решение этого уравнения на отрезке [x₀, x_max], удовлетворяющее начальным условиям: у(х₀) = у₀ (2).

В вычислительной практике более предпочтительным являются численные методы нахождения приближённого решения в фиксированных точках: х₀< x₁< …< x_n=x_max.

Большинство численных методов решения задачи (1) с начальными условиями (2) можно привести к виду: (3).

― при r = 1, а₁ = 1, b₀ = 0 методы вида (3) называются одношаговыми ( чтобы найти y_i₊₁

требуется информация только о предыдущей точке (x_i, y_i)).

― при r > 1 и b₀ = 0 ― явными многошаговыми.

― при r > 1 и b₀ ≠ 0 ― неявными многошаговыми.

Многошаговость нарушает однородность вычислительного процесса, используя для получения недостающей информации другие вычислительные схемы ( например, одношаговые).

А) Метод Эйлера.

х	x₀	x₁	…	х_n
y	y₀	y₁	…	y_n

Для решение Д.У.(1) с Н.У. (2) на отрезке [x₀, x_max] по методу Эйлера, таблица приближённых значений у(х) для равноотстоящих узлов:

строится по формулам: y_k₊₁ = y_k + h∙ f(x_k, y_k)

x_k₊₁ = x_k + h, k = 0, …, n-1, h=(x_n-x₀)/n (4)

Абсолютная погрешность формулы (4) на каждом шаге имеет порядок h²

(5)

Формула (4) означает, что на отрезке [x_k, x_k₊₁] интегральная кривая y = y(x) приближённо заменяется прямолинейным отрезком, выходящим из точки М(х_k; у_k) с угловым коэффициентом f(х_k; у_k). В качестве приближения искомой интегральной кривой получаем ломаную линию с вершинами в точках М₀(х₀; у₀), М₁(х₁; у₁), …, М_n(х_n; у_n). Первое звено касается истинной интегральной кривой в точке М₀(х₀; у₀).

Метод Эйлера может быть применён к решению системы ОДУ и ДУ высших порядков. Последние должны быть предварительно приведены к системе ОДУ первого порядка.

Пусть задана система ОДУ первого порядка: (6)

с начальными условиями: у(х₀) = у₀, z(х₀) = z₀(7)

Приближённые значения у(х_i) ≈ y_i_,z(х_i) ≈ z_i вычисляются по формулам:

(8)

Метод Эйлера обладает двумя существенными недостатками:

1) малой точностью (метод первого порядка точности);

2) систематическое накопление ошибок.

В) Модификации метода Эйлера.

1^ый усовершенствованный метод Эйлера.

Сначала вычисляют промежуточные значения:

(9)

А затем полагают: (10)

2^o^й усовершенствованный метод Эйлера.

Сначала определяют «грубые приближения»: (11)

И приближённо полагают: (12)

Локальная погрешность на i-ом шаге: . Оценка погрешности в точке х_n может быть получена с помощью двойного просчёта (с шагом h и h/2):

(13)

С.) Метод Рунге-Кутта. (4^го порядка)

Наиболее знаменитым из методов Рунге-Кутта является классический метод 4^го порядка

(14)

(15)

Грубая оценка погрешности (двойной просчёт): (16)

Где у(х_i) – точное решение, у^*_i – приближённое решение с шагом h/2, y_i – … с шагом h_.

Для оценки правильности выбора шага h используют равенство:

(17)

q должно равняться нескольким сотым, иначе h уменьшается.

D). Метод Рунге–Кутта 3-го порядка

Многошаговые методы.

(используют информацию о нескольких предыдущих точках)

Д ) Алгоритм Адамса.

Пусть дано дифференциальное уравнение: у′ = f(x, y) (1)

с начальными условиями: у(х₀) = у₀ (1*)

Требуется найти решение уравнения (1) на отрезке [a, b].

Разобьём отрезок [a, b] на n равных частей точками х_i = х₀+ ih (i =0, 1, …, n).

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

Следовательно, определены: у₁, у₂, …, у_k_-1 в точках: х₀+ h, …, x₀+ h(k-1).

2^ойэтап: рекурсивной процедуры. Определение: у_k, y_k₊₁, …, y_n основано на интегрировании интерполяционного многочлена Ньютона.

Рабочие формулы явных методов Адамса (2-го, 3-го, 4-го порядков).

(2)