корнюшин.численные методы

11

Для вывода формулы (3) воспользуемся формулой (1). Поскольку ∆yi= yi+1, из формулы

(1) следует

yi∆vi=∆(yivi)-vi+1∆yi=∆(yivi)-vi+1 yi+1,

отсюда получаем

Формулу суммирования по частям можно использовать для вычисления сумм. Пример 1. Вычислить сумму SN= ∑iN=1 i2i. Положим vi=i, yi=2i, так что

1.1.2. Разностные уравнения

1.1.2.1. Разностные уравнения

Линейное уравнение относительно сеточной функции yi=y(i) (i=0, 1, 2,…)

линейным разностным уравнением m-го порядка. Оно содержит m+1 значение функций y(i). Пользуясь формулами для разностей ∆yi, ∆2yi,…, ∆m-1yi, можно выразить значения yi+1,

yi+2,…, ym+1 через yi и указанные разности: yi+1=yi+∆yi, yi+2=∆2yi+2yi+1-yi=∆2yi+2∆yi+yi и т.д. В

результате из (1) получим новую запись разностного уравнения m-го порядка: a0 (i)yi+ a1 (i)∆yi+…+ am (i)∆myi=f(i), i=0, ±1,±2,... (2)

12

a0(i)yi+a1(i)yi+1+a2(i)yi+2=f(i), a0(i) ≠ 0, a2(i) ≠ 0.

Мы ограничимся изучением разностных уравнений первого и второго порядков.

1.1.2.2. Уравнение первого порядка

Рассмотрим разностное уравнение первого порядка (3). Подставляя yi+1=yi+∆yi, получим

a 0(i)yi+a1(i) ∆yi=f(i), a 0=a0+a1.

Простейшими примерами разностных уравнений первого порядка могут служить формулы

где qi=-a0(i)/a1(i), ϕi=f(i)/a1(i). Отсюда следует, что решение y(i) определено однозначно при i>i0, если задано значение y(i0). Пусть при i=0 задано y0=y(0). Тогда можно определить y1, y2,…, yi,…. Последовательно исключая yi, yi-1,…, y1 по формуле (4), получим

yi+1=qiqi-1…q0y0+ϕi+qiϕi-1+qiqi-1ϕi-2+…+qiqi-1…q1ϕ0,

k =0

т.е. решение разностного уравнения (4) с постоянными коэффициентами.

1.1.2.3. Неравенства первого порядка

Если в выражениях типа (1) или (2) знак равенства заменить знаками неравенства <, >, ≤, ≥, то получим разностные неравенства m-го порядка Пусть дано разностное неравенство первого порядка

k =0

решение неравенства (7).

1.1.2.4. Уравнение второго порядка с постоянными коэффициентами

называется однородным. Его решение может быть найдено в явном виде.

Пусть y i – решение однородного уравнения (12), yi* – какое-либо решение неоднородного уравнения (11). Тогда их сумма yi= y i+ yi* также является решением неоднородного уравнения:

b( y i+1+ yi*+1 )-c( y i+ yi* )+a( y i-1+ yi*−1 )=[b y i+1-c y i+a y i-1]+[b yi*+1 -c yi* +a yi*−1 ]=fi.

Это свойство – следствие линейности уравнения (11); оно сохраняет силу для разностного

уравнения (1) любого порядка. Очевидно, что если y i является решением однородного уравнения

(12), то и c y i, где с – произвольная постоянная, также удовлетворяет этому уравнению.

Пусть yi(1) и yi(2) – два решения уравнения (12). Они называются линейно независимыми,

если равенство

c1 yi(1) +c2 yi(2) =0, i=0, 1, 2,…,

возможно только при с1=с2=0. Это эквивалентно требованию, что определитель системы

отличен от нуля для всех i, m. В частности,

Так же, как и в теории дифференциальных уравнений, можно ввести понятие общего решения разностного уравнения (12) и показать, что если решения yi(1) , yi(2) линейно независимы,

то общее решение уравнения (12) имеет вид

yi= c1 yi(1) +c2 yi(2) ,

где c1 и c2 – произвольные постоянные. Общее решение неоднородного уравнения (11) можно представить в виде

где y *i – какое-либо (частное) решение уравнения (11). Для определения c1 и c2, как и в

случае дифференциальных уравнений, надо задать дополнительные условия – начальные или краевые.

Общее решение уравнения (12) можно найти явно. Будем искать линейно независимые решения уравнения (12) в виде yi=qi, где q ≠ 0 – неизвестное пока число. После подстановки yk=qk в (12) получим квадратное уравнение bq2–cq+a=0, имеющее корни

В зависимости от значений дискриминанта D=c2–4ab возможны три случая.

1) D=c2–4ab>0. Корни q1 и q2 действительны и различны. Им соответствуют два решения yk(1) = q1k , yk(2) = q2k , которые линейно независимы, т.к. отличен от нуля определитель

Заметим, что q1 ≠ 0 и q2 ≠ 0 , иначе a=0, и уравнение (12) не является разностным уравнением второго порядка. Общее решение уравнения (12) имеет вид

2) D=c2–4ab<0. Квадратное уравнение имеет комплексно-сопряженные корни

14

где i – мнимая единица. Эти корни удобно представить в виде q1=ρeiϕ, q2=ρe-iϕ, ρ= ba , ϕ=arctg cD .

Линейно независимыми решениями являются не только функции: q1k =ρkeikϕ=ρk(coskϕ+isinkϕ),

q2k =ρke-ikϕ=ρk(coskϕ-isinkϕ),

но и функции

yk(1) = ρk cos kϕ, yk(2) = ρk sin kϕ,

которые также линейно независимы в силу линейной независимости функций sinkϕ и coskϕ. Общее решение имеет вид

общее решение имеет вид

yk = c1 q0k +c2 kq0k .

1.1.2.5. Примеры

Рассмотрим примеры решения разностных уравнений второго порядка (11). 1. Найти общее решение уравнения

yk+1-2pyk+yk-1=0, a=b=1, c=2p>0.

Возможны три случая:

1)p<1. Положим p=cosα; тогда D=4(cos2α-1)=-4sin2α<0. Линейно независимые решения имеют вид yk(1) = cos kα, yk(2) = sin kα.

2)p>1. Полагая p=chα, получим для q квадратное уравнение q2–2qchα+1=0; его дискриминант равен D=4(ch2α-1)=4sh2α, а корни имеют вид q1,2=chα± shα=e ±α . Линейно независимыми решениями являются функции yk(1) = chkα, yk(2) = shkα.

2. Найти решение уравнения

yk+2-yk+1-2yk=0.

Дискриминант равен D=1+8=9, корнями будут q1,2=(1 ± 3)/2, q1=2, q2=-1. Общее решение имеет вид yk=c12k+c2(-1)k.

15

3. Найти общее решение уравнения

yk+1-yk-6yk-1=2k+1. (18)

Общее решение неоднородного уравнения есть сумма yk = y k + yk* общего решения y k однородного уравнения и частного решения yk* неоднородного уравнения. Найдем сначала общее

решение однородного уравнения. Дискриминант равен D=1+24=25>0, и корни квадратного уравнения q2-q-6=0 равны q1=3, q2=-2, так что yk(1) = 3k , yk(2) = (−2) k . Частное решение yk* будем

искать в виде yk* = c2k , где c=const. Подставляя yk* = c2k в (18), получим c(2k+1-2k-6*2k-1)=c2k-1(- 4)=2k+1, c=-1. Общее решение уравнения (18) имеет вид yk=c13k+c2(-2)k-2k.

1.1.2.6. Разностное уравнение второго порядка с переменными коэффициентами. Задача Коши и краевая задача

Рассмотрим теперь разностное уравнение с переменными коэффициентами

biyi+1-ciyi+aiyi-1=fi, ai ≠ 0, bi ≠ 0, i=0, 1, 2,… (19)

Так как bi ≠ 0, то из (19) получаем следующее рекуррентное соотношение

bi

Выразим yi+1 и yi-1 через yi и разности первого и второго порядков. Тогда уравнение (19) перепишется в виде

∆ yi+(bi-ai)∆yi-(ci-ai-bi)yi=fi, ai ≠ 0, bi ≠ 0.

Решение разностного уравнения первого порядка зависит от произвольной постоянной и определяется однозначно, если задано одно дополнительное условие, например, y0=c0. Решение уравнения второго порядка определяется двумя произвольными постоянными и может быть найдено, если заданы два дополнительных условия. Если оба условия заданы в двух соседних точках, то это задача Коши. Если же два условия заданы в двух разных (но не соседних) точках, то получаем краевую задачу. Для нас основной интерес будут представлять краевые задачи. Введем обозначение Lyi=biyi+1-ciyi+aiyi-1 и сформулируем эти задачи более подробно.

Кроме того, возможны краевые задачи с комбинацией этих краевых условий: при i=0 – условия одного типа, при i=N – условия другого типа.

16

Решение задачи Коши находится непосредственно из уравнения (21) по рекуррентной формуле (20) с учетом начальных данных y0=µ1, y1=µ2. Решение краевых задач находится более

y0=c1=0, yN=c2N+N2/2=0, c2=-N/2. Таким образом, yi=-iN/2+i2/2=-i(N-i)/2 есть решение задачи (27).

1.1.3. Решение разностных краевых задач для уравнений второго порядка

1.1.3.1. Решение разностных краевых задач методом прогонки

Краевая задача

aiyi-1-ciyi+biyi+1=-fi, ai ≠ 0, bi ≠ 0, i=1, 2,…, N-1, y0=λ1y1+µ1, yN=λ2yN-1+µ2 (1)

представляет собой систему линейных алгебраических уравнений с трехдиагональной матрицей

Зная α1 и β1 и переходя от i к i+1 в формулах (4) и (5), определим αi и βi для всех i=2, 3,…, N. Вычисления по формуле (3) ведутся путем перехода от i+1 к i (т.е. зная yi+1, находим yi), и для

17

начала этих вычислений надо задать yN. Определим yN из краевого условия yN=λ2yN-1+µ2 и условия

(3) при i=N-1: yN-1=αNyN+βN. Отсюда находим

Соберем все формулы прогонки и запишем их в порядке применения

Стрелки показывают направление счета: (→) от i к i+1, (←) - от i+1 к i.

Таким образом, краевая задача для уравнения второго порядка сведена к трем задачам Коши для уравнений первого порядка.

1.1.3.2. Устойчивость метода прогонки

Формулы прогонки можно применять, если знаменатели дробей (8) и (10) не обращаются в нуль. Достаточными условиями этого являются неравенства

причем одно из первых двух неравенств второй строки должно быть строгим. Покажем, что при условиях (11) знаменатели ci-aiαi и 1-αNλ2 не обращаются в нуль и

1 −αN λ2 ≥1 − αN λ2 ≥1 − λ2 > 0 . Таким образом, при выполнении условий (11) задача (1)

имеет единственное решение, которое мы находим по формулам прогонки (8) – (10). Вычисления по формулам (8) – (10) ведутся на компьютере приближенно, с конечным

числом значащих цифр. В результате погрешностей округления фактически находится не функция

ли в ходе вычислений возрастание погрешности округления, что может привести как к потере точности, так и к невозможности продолжать вычисления из-за роста определяемых величин? Примером может служить нахождение yi по формуле yi+1=qyi при q>1. Поскольку yn=qny0, для

любого y0 можно указать такое n0, при котором yn0 будет машинной бесконечностью. Фактически

~

в силу погрешностей округления определяется не точное значение yi, а значение yi из уравнения

18

δyi+1=qδyi+η (i=0, 1,…, δy0=η). Из формулы δyi=qiη+η(q1-1)/(q-1) следует, что погрешность δyi при q>1 экспоненциально растет с ростом i.

Вернемся к методу прогонки и покажем, что при αi ≤1 погрешность δyi не нарастает. В

Если учесть, что в ходе вычислений возмущаются и коэффициенты αi+1, βi+1, то можно показать, что погрешность δyi пропорциональна квадрату числа узлов N: max δyi ≤ ε0 N 2 , где ε0 –

погрешность округления. Отсюда видна связь между требуемой точностью ε решения задачи, числом N уравнений и числом значащих цифр компьютера, поскольку ε0N2 ≈ ε.

1.1.3.3. Другие варианты метода прогонки

Рассмотренный выше метод прогонки (8) – (10), при котором определение yi производится последовательно справа налево, называют правой прогонкой. Аналогично определяются формулы

левой прогонки:

получим (13) и (14). Значение y0 находим из условия y0=λ1y1+µ1 и формулы y0=ξ1y1+η1. Из неравенств ci −biξi+1 ≥ ci − bi ξi+1 ≥ ai + bi (1− ξi+1 ), 1−ξ1λ1 ≥1− ξ1 λ1 следует, что условия (11) гарантируют применимость формул левой прогонки и их вычислительную устойчивость, т.к.

ξi ≤1 (i=1, 2,…, N).

Комбинация левой и правой прогонок дает метод встречных прогонок. В этом методе в области 0 ≤ i ≤ i0 +1 по формулам (8), (9) вычисляются прогоночные коэффициенты αi, βi, а в

области i0 ≤ i ≤ N по формулам (13), (14) находятся ξi и ηi. При i=i0 производится сопряжение решений в форме (10) и (15).

i<i0, а по формуле (15) – значения yi при i>i0. Вычисления при i>i0 и i<i0 проводятся автономно (имеет место распараллеливание вычислений). Метод встречных прогонок особенно удобен, если, например, требуется найти yi лишь в одном узле i=i0.

19

20

Модуль 2. Решение уравнений и задачи интерполяции

2.2. Численное решение алгебраических и трансцендентных уравнений

Задача численного решения уравнения распадается на две:

1)задача отделения корней – нахождение областей, которым принадлежат корни уравнений;

2)задача численного нахождения приближенных значений корня (с заданной степенью точности).

2.2.1. Задача отделения корней

Существует несколько методов отделения корней уравнения.

1. Главный метод – знание свойств функций, входящих в уравнение. Например, в выражении

x 2 − 3x + 5 = 0

5 + ∑25k =1 x 2k

нет необходимости рассматривать знаменатель, т.к. он никогда не обращается в нуль.

2. Графические методы отделения корня

а) На вещественной оси (построение таблицы значений функции). Пусть дана функция

P(x) = 0,−∞ < x <+ ∞.

Т.к. ось бесконечна, необходимо построение провести в два этапа. На первом разбивают сегмент [-1,1] на сколь угодно малые части и получают значения функции в точках разбиения. На

задача свелась к поиску корней вещественных функций. Эти кривые строятся в декартовой системе координат, где выделяются области пересечения кривых Q(x, y) = 0 и L(x, y) = 0, как показано на рис.2.1.

3. Метод малого параметра