Численные методы. Лекции. Часть 2
.pdfЧасто в алгоритмах выбора шага целесообразно использовать не абсолютную погрешность - , а относительную - /|y|. Например, для компонент искомой вектор-функции, которые растут и становятся очень большими. Нельзя же использовать относительную погрешность в тех случаях, когда компонента может обратить-
ся в нуль. Эти обстоятельства и вынуждают нас для контроля вычислительного процесса использовать меру погрешности.
Определение: Мерой погрешности приближенного значения решения СОДУ (17.1) в точке xj+1 называется величина
μ = (μ1, μ2, . . . , μn), определяемая соотношением
|
i |
= |
|
|
ji |
+1 |
, |
|yi |
|
| |
|
|
(19.1) |
μ |
| ij+1,| |
+1 |
|
P i |
|||||||||
|
|
|
|
yi |
|
yji |
|
> P i |
|
||||
|
|
|
|
|
j+1 |
|
| j |
+1| |
|
|
|||
где P i, j = 1, . . . , n |
-некоторые фиксированные положительные |
||||||||||||
числа. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Контроль точности по мере погрешности состоит в том, что на тех участках интервала интегрирования, где абсолютная величина решения не превосходит некоторого значения P i, контроль точности ведется по абсолютной погрешности, а там, где абсолютная величина решения превосходит это значение, контроль точности ведется по относительной погрешности.
Для СОДУ (17.1) с проверкой на точность могут вычисляться либо все компоненты решения, либо некоторые из них.
Контроль точности может вестись покомпонентно или по норме. Для различных компонент могут использоваться как различные характеристики точности (абсолютная, относительная погрешность, мера погрешности), так и различные допустимые значения погрешности,т.е. ε = (ε1, ε2, . . . , εr), где r n , r− количество проверяемых на точность компонент решения.
Те компоненты решения, которые проверяются на точность по мере погрешности (19.1) , могут иметь каждая своё значение P i
для перехода от абсолютной погрешности к относительной. В этом случае P = (P 1, . . . , P r ).
Контроль точности по норме означает, что контролируется некоторая норма оценки погрешности j+1 .
111
Часто используются нормы:
∞ = max | i|,
1 i n
n
1 = | i|,
i=1
n
2 = |
i |
| i|2 . |
|
|
=1 |
§20. Качество алгоритма.
Бросая в воду камешки, смотри на круги, ими образуемые; иначе такое бросание будет пустою забавою. Козьма Прутков.
Здесь будем рассматривать, только три критерия качества алгоритма:
•- надежность;
•- точность ;
•- объём вычислений.
Надежность.
Так как при практической реализации методов пытаются регулировать величину локальной погрешности, метод можно считать надежным, если он удачно с этим справляется. Это значит, что необходимо вычислять на каждом шаге
δjε+1 = |
|lj+1| |
, |
(20.1) |
|
hj ε |
||||
|
|
|
112
lj+1− истинная локальная погрешность на шаге hj , |
или |
||
ξjε+1 = |
|lj+1| |
. |
(20.2) |
|
| j+1| |
|
|
Вычисленные значения (20.1), (20.2) можно использовать как для проверки качества используемого алгоритма, так и для его усовер-
шенствования.
Точность.
Численному анализу подвергается погрешность решения в каждом узле (абсолютная,относительная), обеспечивая ответы на следующие вопросы:
•- непрерывно ли уменьшается полная погрешность Rxj+1 при уменьшении задаваемой допустимой погрешности ε ?;
•- правильно ли работает алгоритм, когда требуется высокая точность?;
Объем вычислений.
Для одношаговых методов такой характеристикой служит количество вычислений правой части Θ(ε) СОДУ (17.1) на интервале интегрирования [X0, Xend] для каждой заданной точности ε.
§21. Автоматический выбор шага интегрирования.
Применение переменного шага интегрирования позволяет учитывать характер поведения решения и уменьшать общее число шагов, сохранив при этом требуемую точность приближенного решения. Имея в распоряжении способы оценки локальной погрешности (15.8), (15.9),(16.6), приближенного метода, величину шага интегрирования можно выбирать автоматически в процессе
счета.
Алгоритмы использующие удвоение и деление шага пополам.
Алгоритм использующий оценки (15.8), (15.9). Эти оценки локальной погрешности одношагового m - этапного метода типа Рунге-Кутты требуют (3m−1)− ого вычисления правой части исходного уравнения. Такие огромные вычислительные затраты вы-
113
нуждают нас строить алгоритм использующий все полученные при-
ближения к решению y¯i+1,h , y˜i+ 12 , h2 , y˜i+1, h2 ,.
Пусть i+1 - оценка локальной погрешности метода на шаге hi, допущенная при вычислении приближенного значения решения y¯i+1,h в точке xi + hi, hi = h = const > 0
Рассматриваемый ниже алгоритм, предусматривает четыре альтернативных варианта принятия решения:
•Если оценка локальной погрешности превосходит некоторую
наперед заданную границу ε :
i+1 > ε · 2s,
то считается, что приближенное значение решения y¯i+1,hi не удовлетворяет предписанной точности. Уменьшая шаг в два раза hi = 12 hi , необходимо по той же приближенной формуле вычислять новое значение y¯i+1,hi в точке xi + hi ;
• Оценка локальной погрешности i+1
2sε+1 i+1 ε
приближенного значения решения y¯i+1,hi удовлетворяет предписанной точности. Увеличение шага интегрирования в два раза hi+1 = 2hi , выведет погрешность приближения за рамки допустимого. В качестве приближения к решению в точке xi +hi выбирается y¯i+1,hi . Шаг остается неизменным hi+1 = hi;
• Оценка локальной погрешности i+1
ε < i+1 ε · 2s,
приближенного значения решения y¯i+1,hi не удовлетвоpяет предписанной точности. Но в качестве искомого решению может быть использовано приближение y˜i+1, h2i ,т.е. yi+1 ≡
y˜i+1, h2i . Шаг интегрирования для продолжения hi+1 = h2i ;
• Оценка локальной погрешности i+1
ε
i+1 < 2s+1 ,
114
приближенного значения решения y¯i+1,hi существенно меньше заданной. Рекомендуется увеличение шага интегрирования в два pаза hi+1 = 2hi . В качестве приближения к решению в точке xi + hi выбирается y¯i+1,hi .
§22. Алгоритм выбора начального шага.
a) |
Вычислим f x0, y(x0) |
в начальной точке x0 ; |
|
|||
b) |
найдем |
max |X01|, |Xend| |
s+1 + f x0, y(x0) s+1 |
|
||
|
= |
, |
||||
|
|
|
|
|
|
|
c) тогда начальный шаг равен
h = ε
1 (s+1)
Часто, начальные условия находятся в особом положении, где большинство компонент f i x0, y(x0) i = 1, . . . , n может оказаться нулями.
В этом случае к a) − c) необходимо добавить ещё два шага.
d) |
Сделать один шаг методом Эйлера с длиной шага h, полу- |
|
ченной в c) ; |
e) |
повторить шаги алгоритма a) − c) с новым значением и вы- |
|
брать меньший из двух полученных длин шагов. |
§23. Недостатки явного метода Рунге-Кутты.
•Зависимость порядка точности метода от количества вычислений правой части ;
•Оценка погрешности требует дополнительных вычислительных затрат сравнимых по объему с вычислительными затратами на получение приближенного решения;
115
•При решении жестких задач Коши их использование нерентабельно:
§24. Примеры жестких задач Коши |
|
||
Рассмотрим линейное уравнение |
|
||
|
dy |
= λy. |
(24.1) |
|
|
||
|
dx |
|
|
Требуется найти приближение к решению удовлетворяющее начальному условию:
y(0) = y0. |
(24.2) |
Пусть λ < 0. Для нахождения приближения к решению воспользуемся явным методом Эйлера:
yj+1 = yj + hλyj = (1 + λh)yj . |
(24.3) |
Точное решение задачи (24.1),(24.2)
y(x) = eλxy0 |
(24.4) |
монотонно убывает, y(x) → 0, сохраняя знак, когда x растет. А значит, необходимо, чтобы решение разностной задачи (24.2),(24.3) также стремилось к нулю при x → ∞. Но это будет возможно для метода Эйлера только при условии выполнения неравенства
0 < 1 + λh < 1 |
(24.5) |
т.е. для
|λ|h < 1 |
(24.6) |
Для двухэтапного метода Рунге-Кутты второго порядка точности расчетная схема численного интегрирования (24.1),(24.2) имеет вид:
|
1 |
|
h2 |
|
yj+1 = yj + |
|
(λhyj + λh(yj + λhyj )) = (1 + λh + λ2 |
|
)yj . (24.7) |
2 |
2 |
|||
116
Решение задачи (24.7),(24.3) yj монотонно убывает , если
0 < 1 + λh + λ2 |
h2 |
< 1. |
(24.8) |
2 |
|||
Но это возможно, если |
|
|
|
− 2 < λh < 0, → |
|
|λ|h < 2. |
(24.9) |
Аналогично можно получить ограничения на величину шага для явных методов Рунге-Кутты более высокого порядка точности, так как все они представимы в виде:
yj+1 = Ps(λh)yj , |
(24.10) |
где Ps(λh) - многочлен степени s от λh. И значит их применение возможно только при выполнении условий
|λ|h < const. |
(24.11) |
Для каждого λ существует δ(λ) : такая , что при |
x > δ(λ) |
eλx |
|
фактически не вносит никакого вклада в решение. Однако, ограничение (24.11), для сохранения устойчивости явного метода, не позволяет в этом случае увеличить шаг интегрирования. Рассмотрим более общее скалярное уравнение
dy |
= λy + |
dF (x) |
− λF (x). x 0, y(0) = y0, λ << 0 (24.12) |
|
|
||
dx |
dx |
добавив в правой части в качестве возмущения F (x) – медленно меняющуюся функцию от x. Решение задачи Коши y(x) имеет вид
y(x) = F (x) + eλx [y0 − F (0)] . |
(24.13) |
Здесь, как и в предыдущем примере, уже после небольшого отрезка времени переходная часть решения, eλx [y0 − F (0)] – жесткая компонента решения (сильно меняющаяся компонента), в реше-
ние y(x) фактически не вносит никакого вклада. Независимо от
117
начального значения y0 в решении на большей части отрезка интегрирования преобладает медленно меняющаяся функция F (x) . Решение (24.12) в момент времени x связано с решением в момент времени x + h :
y(x + h) = F (x + h) + eλh [y(x) − F (x)] . |
(24.14) |
Но отсюда следует, что существующие в любой момент времени x возмущения медленно меняющегося решения F (x) быстро затуха-
ют. Медленно меняющиеся компоненты решения называют непереходными или гладкими.
Сравним аппроксимацию, определяемую явным методом Эйлера, с
точным решением для (24.12) y(xn+1), |
xn+1 = xn + h |
Имеем: |
|||||
|
y(xn+1) = F (xn+1) + eλh [y(xn) − F (xn)] , |
(24.15) |
|||||
yn+1 |
|
dF (x) |
x=xn +(1 + hλ) [yn − F (xn)] , |
(24.16) |
|||
= F (xn) + h |
dx |
||||||
|
|
|
|
|
|
|
|
Разность |
y(xn) − F (xn) |
интерпретируется |
как возмущение глад- |
||||
кого решения F (x) в момент времени |
x = xn. Это возмуще- |
||||||
ние быстро убывает из-за экспоненты с отрицательным показателем eλh, λh << 0.
Подобным образом можно интерпретировать и разность yn − F (xn) в (24.16). Численный метод должен быть в состоянии подавить эти разности для значений λh << 0, и h должно определяться только в зависимости от изменений функции F (x). Разность yn − F (xn) и при интегрировании (24.12) подавляется при сильных ограничениях на шаг |hλ| < 2 , которое не снимается даже в случае если yn − F (xn) исчезающе мала.
Эта ситуация характерна для жестких уравнений: решение содержит член, вклад которого очень мал, но обычные методы для сохранения устойчивости требуют, чтобы этот член аппроксимировался достаточно точно,т.е. величина шага ограничивается скорее численной устойчивостью, чем точностью. Очень сильная устойчивость дифферен-
циального уравнения оказывается недостатком с точки зрения распространения погрешности численного решения при применении явных методов.
118
Рассмотрим использование, для интегрирования дифференциальных уравнений такого типа, неявных методов, например, Эйлера:
yj+1 = yj + hf (xj , yj+1). |
(24.17) |
Так при интегрировании дифференциального уравнения (24.1) по схеме (24.17) приближение к решению будем получать:
yj+1 = yj + λhyj+1 −→ yj+1 = |
1 |
yj . |
(24.18) |
|
|||
1 − λh |
В этом случае применение (24.17) обеспечивает монотонное убывание yn.
y2
y0
x0
y3
y1
Рис. 5 Поведение явного метода Эйлера
119
y0
y1
y2 y4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x0 |
x |
1 |
x |
2 |
x4 |
|
Рис. 6 Поведение неявного метода Эйлера
Для жестких дифференциальных уравнений характерно поле направлений, изображенное на рис.5 .
Неявный метод Эйлера вполне подходит и для решения (24.12). Аппроксимация в этом случае выполняется по схеме:
yn+1 = (1 − hλ)−1 F (xn+1) + h |
dx |
x=xn+1 |
−hλF (xn+1) + |
||||
|
|
|
|
dF (x) |
|
|
|
+(1 |
1 |
|
|
|
|
(24.19) |
|
− hλ)− [yn − F (xn)] , |
|
|
|
||||
Разность |
yn −F (xn) быстро убывает. Для любого фиксированного |
||||||
h > 0 , |
yn+1 → F (xn+1) при hλ → −∞. |
|
|
|
|||
Для линейных систем |
|
|
|
|
|||
|
|
dy(x) |
= Ay(x), |
|
|
(24.20) |
|
|
|
|
|
|
|||
|
|
dx |
|
|
|
|
|
(A - постоянная матрица), такие различные компоненты решения |
|||||||
(жесткие и гладкие) возникают, когда матрица Якоби |
A содержит |
||||||
сильно различающиеся по величине собственные значения. Рас-
120
