Документ Microsoft Office Word (3)
.doc1. Ошибки в численных расчетах
1.1. Типы ошибок
Анализ ошибок в полученных численно результатах должен являться непременной
составной частью любого серьезного расчета. Ошибки могут содержаться как в исходной
информации, так и вноситься в результате вычислений. Введем понятия абсолютной и
относительной ошибок.
Абсолютная ошибка – это разность между истинным и приближенным значениями
величины
. xexx...
Относительная ошибка – это отношение абсолютной ошибки к приближенному
значению
. xeexx..
Для - , для и для - абсолютная и относительная ошибки
– совершенно разные величины.
1~xxeexx..1..x1..x
Различают три вида ошибок: 1) ошибки в исходной информации; 2) ошибки при
ограничении бесконечного математического процесса конечным числом операций
(ошибки ограничения); 3) ошибки представления числа конечной последовательность
значащих цифр (ошибки округления).
Ошибки в исходной информации могут быть вызваны неточностями измерения,
невозможность представить число конечной дробью или грубыми просмотрами.
С последним все ясно – следует всегда быть внимательным и тщательно проверять
представляемые к расчету данные.
Неточности измерения связаны главным образом с точностью измерительных
приборов. Так, если измерение длины производится при помощи линейки со шкалой 1 мм,
то возможная ошибка будет равна 0.5 мм. Кроме того, иррациональные числа (например:
, 1/3) невозможно представить конечной дробь, а конечные дроби в одной системе
счисления могут быть бесконечными в другой. Так число 1/10 в двоичной системе
счисления представляет собой бесконечную дробь: 0.00011001100110011… с периодом
0011. Поэтому 0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1 может быть не равно 1.
.
Ошибки ограничения. Примером может служить вычисление функции при
помощи разложения ее в ряд Тейлора
xsin
. ......
!7!5!3sin753xxxxx
Имеем бесконечное множество элементов ряда, следовательно, чтобы результатом
вычисления был точное число, необходимо произвести определенные вычисления
бесконечное количество раз, что невозможно.
Ошибки округления. Приведем пример с нормализованными числами. В этом случае
действительное число представляется в виде десятичной дроби (мантиссы) f, умноженной
на целую степень десяти s:
. sfx10..
Например
; ; . 7234107234.04..46.32103246.02..0001627.0101627.03...
Число значащих цифр мантиссы будем обозначать буквой t, степень основания десяти
для большего числа – буквой s.
Для примера сложим два числа и определим абсолютную и относительную ошибки
результата сложения. При этой операции (как и при вычитании) компьютер сначала
сравнивает порядки чисел, затем мантисса меньшего числа сдвигается вправо на столько
разрядов, сколько необходимо, чтобы порядки стали одинаковыми и только после этого
производится операция сложения. После операций сложения или вычитания получаем
число
, (1.1) tszszgfz.....1010
в котором присутствует остаток , являющийся абсолютной ошибкой. tszg..10
Например, сложим числа и . Их представление в нормализованном виде
и . , , второе число после подготовки к сложению примет
вид . В формуле (1.1), после сложения, получим: , ,
.
723446.32
4107234.0.2103246.0.4.s4.t
410003246,0.0..ts7266.0.xf
46.0.xg
Очевидно, что, при отбрасывании остатка, максимальные абсолютная и
относительная ошибки равна, соответственно,
, , ...zemax..tstszg.....10110max
..
..
110101.010110min10maxmax..
..
.
.
.
.
.
.
.
...
...
tstssztszzfgze
при округлении (анализируя величину ) 5,0..zg
, . ..tstszg.....105.010max1105.0101.0105.0max..
.
..
.
.
.
...
...
tstsяze
1.2. Распространение ошибок округления.
Рассмотрим снова сложение.
. Здесь — ......yxyxyxeyxeeyxeyexyx.............yxyxeee...
абсолютная ошибка. Распространение абсолютных и относительных ошибок при
сложении определяется по формулам
, . ..
.
.
..
.
.
.
...
.
..
.
.
.
.
.
yeyxyxeyxxyxeyxyx
Аналогично можно составить табличку распространения ошибок, возникающих при
- вычитании
, . yxyxeee.....
.
.
..
.
.
.
...
.
..
.
.
.
.
.
yeyxyxeyxxyxeyxyx
- умножении
, . xyyxeyexe.....
.
.
..
.
.
...
.
..
.
.
.
.
yexeyxeyxyx
- делении
. yxyyxyxyxeyxeyyxyeyeyexyeyexeyexyx221111
...
.
.
.
.
.
.
.
.
...
.
.
..
.
.
...
.
.
..
.
.
..
.
.
.
.
.
.
.
.
..
(здесь отброшены величины, имеющие 2-ой и выше порядки относительно ).
Следовательно
e
, . yxyxeyxeye21
....
.
.
..
.
.
...
.
..
.
.
yexeyxeyxyx
1.3. Графы вычислительных процессов.
Рассмотрим операции сложения и умножения чисел с исходными
относительными ошибками (округления) :
zyx,,
zyxeee,,
, , yxv....yxzu..
где - ошибка округления при сложении. При умножении появляется ошибка округления
. Полная ошибка результата:
1e
2e
,, 2111eeeeyxyeyxxvezeuezyxvzu......
.
.
..
.
.
.
.
.
.
...
где - ошибка округления при умножении
При симметричном округлении ошибки и tzyxeeeee.......10521
.........
.
.
..
.
.
...
.
..
.
......tttttuyxyyxxue10511051105105105
. tyxyyxx.....
.
.
..
.
.
.
.
.
.
.1053
Если и , то 0.x0.y
и . 1.
.
.
.yxyyxx..110210531.........ttuue
2. Алгебраические и трансцендентные уравнения
Решение алгебраических и трансцендентных уравнений может представлять собой
самостоятельную задачу или являться составной частью более сложных задач. Задачи,
сводящиеся к решению алгебраических и трансцендентных уравнений, можно
классифицировать по числу уравнений и в зависимости от предполагаемого характера и
числа решений (рис.1). Уравнение или систему уравнений будем называть линейной или
нелинейной в зависимости от математической природы входящих в нее уравнений.
Рис. 1. Классификация уравнений.
Обычно, нелинейные уравнения делят на трансцендентные и алгебраические.
Нелинейные уравнения, содержащие тригонометрические функции или другие
специальные функции, например или , называются трансцендентными. Уравнения,
содержащие суммы целых степеней х, называются алгебраическими. Общий вид
последних
xlgxe
. 0...0111......
.axaxaxannnn
Решение линейного уравнения с одним неизвестным получается достаточно просто и
здесь не рассматривается. Цель данной главы — изложение различных методов решения
уравнений, относящихся к остальным четырем типам.
2.1. Численное решение нелинейных уравнений с одним неизвестным
Методы решения нелинейных уравнений такого типа делятся на прямые и
итерационные. Первые позволяют найти решение непосредственно с помощью формул и
всегда обеспечивают получение точного решения. Известным примером такого рода
является формула корней квадратного уравнения. В итерационных методах задается
процедура решения в виде многократного применения некоторого алгоритма. Полученное
решение всегда является приближенным, хотя может быть сколь угодно близким к
точному. Итерационные методы наиболее удобны для реализации на ЭВМ и поэтому
подробно рассматриваются в этой главе.
2.1.1. Постановка задачи
В каждом из излагаемых методов считается, что задача состоит в отыскании
действительных корней —точек, в которых функция f(x) обращается в 0
f (x) = 0. (2.1)
Графически это выглядит следующим образом (рис. 2). Дано уравнение
y = f (x), (2.2)
следует найти точки пересечения функции f(x) с осью абсцисс.
Рис. 2
2.1.2. Алгоритм нахождения корней
Алгоритм численного нахождения корней включает 2-а этапа:
1-й — отделение или локализация корней (нахождение промежутков оси x,
содержащих только один корень),
2-й — вычисление корней с заданной точностью ..
Если x — точное значение корня уравнения (2.1), то в качестве искомого
приближенного значения может быть принято любое значение , удовлетворяющее
условию
..ix
или , (2.3) ........1iixx......ixf
где надстрочный индекс в скобках — номер итерации. i
2.1.3. Отделение корней
Численная процедура отделения корней заключается в разбиении участка оси х [a, b],
на котором ищутся корни, на n равных отрезков длиной h=(b-a)/n точками
. Затем последовательно анализируется
знаки функции на концах каждого отрезка (для i-го — f(xi) и f(xi-1)) и если они отличаются,
012,,2,...,nxaxahxahxxnhb........
то очевидно на данном отрезке лежит корень. Формально условие наличия корня на
интервале [xi-1, xi] можно записать следующим образом
f(xi).f(xi-1)<0. (2.4)
Блок-схема алгоритма отделения корней представлена на рис 3. Заметим, что если
есть возможность построить график функции, то отделение корней легко произвести
визуально.
Рис. 3
Далее, считая, что интервал локализации корня найден [x1, x2], перейдем к методам
вычисления корней с заданной точностью.
2.1.4. Метод половинного деления (бисекций)
Идея метода заключается в делении отрезка, на котором находится корень пополам,
выборе той из половин, на которой остался корень еще раз пополам и т. д. до тех пор пока
не будет выполнено одно из условий (2.3). Сходится для любой непрерывной функции
(2.1). На рис. 3 процедура показана графически. После локализации корня, по формуле
вычисляется 1-ое приближение (среднее значение х) в интервале
значений [х1, х2] и находится значение функции в точке . Если знак
,то в дальнейшем вместо используется , в противном случае
используется вместо . В результате интервал, в котором заключено значение корня,
сужается. На следующей итерации процедура повторяется с новыми значениями х1 и х2,
вычисляется , находится и т.д. Итерации продолжаются, пока не будет
выполнено одно из условий (2.3).
..1ср21()/2xxx..
....1срxf..1срx
......011ср.xfxf1x..1срx..1срx
2x
..2срx....2срxf
Рис. 4. Графическая интерпретация метода половинного деления блок схема
На рис. 5 представлена блок-схема алгоритма метода половинного деления. Хотя
метод не обладает высокой вычислительной эффективностью, с увеличением числа
итераций он обеспечивает получение все более точного приближенного значения корня.
Ширина интервала, в котором заключен корень после N итераций убывает в 2N раза, при
этом очевидно, что, если x –точное решение, то
. ..
.
..NNxxxx212
Рис. 5. Блок-схема метода половинного деления
2.1.5. Метод хорд
В основе этого метода лежит линейная интерполяция по двум значениям функции,
имеющим противоположные знаки. При отыскании корня этот метод обеспечивает более
быструю сходимость, чем предыдущий. На рис. 6 процесс решения показан графически.
2x
1x
Рис. 6. Метод хорд.
..2*1xx.
..1*1xx.
x
y
Уравнение линии, проведенной через точки , можно представить
в виде
....11,xfx....22,xfx
.
........121211xfxfxxxfxfxx
.
.
.
.
.
Приравнивая , получим 1-ое приближение для корня ..0.xf
. ....
....1212111*xfxfxxxfxx
.
.
..
Это значение аргумента используется для определения значения функции , которое
сравнивается со значениями функций и , в дальнейшем используется
вместо того из концов интервала, в котором знаки функций совпадают. На следующей
итерации процедура повторяется с новыми значениями х1 и х2, вычисляется ,
находится и т.д. Итерации продолжаются, пока не будет выполнено 2-е из условий
(2.3). На рис. 7 дана блок-схема алгоритма метода хорд.
....1*xf
..1xf..2xf..1*x
..2*x
....2*xf
Стоп
Вывод
..ix*
Да
......ixf*
........iixfxfxx*2*2,..
Начало
......01*.xfxfi
Ввод x1, x2, .
Рис. 6. Блок-схема метода хорд.
Нет
Да
..
......iixfxfxx*1*1,
.
.
Вычисление и ..ix*
....ixf*
2.1.6. Метод Ньютона (метод касательных)
Является одним из наиболее часто используемых методов решения нелинейных
уравнений. В отличие от двух предыдущих методов для нахождения корня при помощи
метода Ньютона не требуется знать заранее интервал изоляции корня. Для поиска корня
осуществляется экстраполяция с помощью касательной к кривой в данной точке.
Формально, в основу метода положено разложение функции f(x) в ряд Тейлора
.........xfhxfhxfhxf.......
22
Отбросим элементы, содержащие во второй и более высоких степенях, заменим
начальным приближением и используем соотношения или ,
где — 1-е приближение. Предполагая, что переход от к приближает значение
функции к нулю так, что , получим 1-е приближение для корня
hx
..0x....10xhx......01xxh..
)1(x..0x..1x
....00..hxf
. ............0001xfxfxx...
Далее, заменяем значение значением и повторяем процедуру. Счет прекращается,
когда величина станет достаточно малой , т.е. выполняется 1-е
из условий (2.3).
........11....iixfxft..t
На рис. 7 показана графическая интерпретация данного метода, на рис. 8 — блок-
схема алгоритма метода. Значение соответствует точке, в которой касательная к
кривой в точке пересекает ось х. Так как кривая f(x) отлична от прямой, то значение
функции , скорее всего не будет в точности равно нулю. Поэтому вся процедура
повторяется, причем вместо используется .
..1x
..0x
....1xf
..0x..1x
Рис. 7. Метод Ньютона.
..2x
..0x
..1x
x
y
Быстрота сходимости в большой мере зависит от удачного выбора исходной точки. Если в
процессе итераций тангенс угла наклона касательной f.(х) обращается в нуль, то
применение метода осложняется. Можно также показать, что в случае бесконечно
большого f..(х) метод также не будет достаточно эффективным. Так как условие кратности
корней имеет вид f(x)=f.(х)=0, то в этом случае метод Ньютона не обеспечивает
сходимость.
....iixx..1
Стоп
Вывод
..ix
Начало
Ввод ...,0x
Рис. 8. Блок-схема метода Ньютона
Нет
Да
Вычисление
....txxii...1
Обычно принимают или , смотря по тому, в какой из этих точек знак
функции совпадает со знаком второй производной ( и - концы интервала
локализации корня).
..
10xx...
20xx.
1x
2.1.7. Модифицированный метод Ньютона.
Один из недостатков метода Ньютона состоит в том, что, пользуясь им, приходится
дифференцировать функцию f(x). Если нахождение производной затруднено, то можно
воспользоваться некоторым приближением, что и составляет особенность
модифицированный метода. Заменив производную f.(х), используемую в методе Ньютона
, ............111......iiiixfxfxx
разностным аналогом
, ....
........
....21211
..
..
.
.
.
..
iiiiixxxfxfxF
где – предыдущее (или нулевое) приближение вычисляемого корня, получим
следующую итерационную формулу:
..2.ix
. ............111......iiiixFxfxx
Схема алгоритма для этого метода та же, что и для метода Ньютона (несколько иной вид
имеет итерационная формула). В сущности, в этом методе для отыскания корня
используется комбинация интерполяции и экстраполяции. В своей интерполяционной
части этот метод эквивалентен методу хорд. Как и в случае метода Ньютона, счет
заканчивается, когда последовательные значения х совпадают с некоторой приемлемой
точностью или когда значение функции f(х) становится достаточно близким к нулю. В
случае кратных корней при использовании метода возникают те же трудности, что и при
использовании метода Ньютона
2.1.8. Метод простых итераций
Для применения этого метода уравнение f(x)=0 представляется в следующем виде:
, ..xgx.
для чего достаточно просто добавить к его левой и правой частям значения x.
Соответствующая итерационная формула имеет вид
. ......1..iixgx
Блок-схема алгоритма метода представлена на рис. 7. Выбирается подходящее
нулевое значение корня x0 (обычно в интервале локализации корня), по итерационной
формуле вычисляется 1-ое приближение x1, затем 2-ое – x2 и т.д., пока не будет достигнута
требуемая точность. Числовую последовательность называют
итерационной последовательностью. Простота метода делает его привлекательным,
однако, не следует забывать, что и этому методу присущи недостатки, так как он не всегда
обеспечивает сходимость. Поэтому для любой программы, в которой используется этот
алгоритм, необходимо предусматривать контроль сходимости и прекращать счет, если
сходимость не обеспечивается.
nxxxx,,,,210.
........1iixx
Стоп
Вывод
Начало
Ввод x0,
Рис. 6. Блок-схема алгоритма метода итераций.
Нет
Да
Вычисление
......1..iixfx
2.1.9. Теорема о сходимости метода простой итерации.
Теорема. Пусть уравнение x=f(x) имеет единственный корень на отрезке [a, b] и во
всех точках этого интервала производная f(x) удовлетворяет неравенству
1)(...Mxf
Если при этом выполняется условие a. f(x). b, то итерационный процесс сходится,
причем за нулевое приближение x0 можно взять любую точку интервала [a, b].
Доказательство. Пусть x0 - любая точка интервала .a, b], x1= f(x0) — первое
приближение. Если x — точное значение корня, то по теореме Лагранжа о конечных
приращениях получим
x-x1= f(x)-f(x0)=(x-x0).f.(.0), .0.[a, b]
0001)(xxMfxxxx.........
Для второго приближения x2= f(x1) и учитывая, что по условию теоремы х1.[a, b],
получим
. ],[ ),()()()(11112bafxxxfxfxx..........
Отсюда и из предыдущей оценки получим
. 022xxMxx....
Повторяя данный процесс оценки приближений, через n шагов будем иметь
неравенство:
. 0xxMxxnn....
В силу условия M< — и . 0)(lim..
..
nnxxxxn.
..nlim
Из неравенства следует оценка точности приближения.
2.1.10. Оценка погрешности метода итераций
При выполнении условий теоремы итерационная последовательность сходится при
любом выборе начального значения x0. Получим формулу, дающую способ определения
погрешности n-го приближения. Пусть xn - приближение к истинному значению корня
уравнения x=f(x). Абсолютная ошибка этого приближения оценивается расстоянием
между истинным и полученным значением корня: Без вывода приведем
формулу
nnxxx...
. 11..
.
..nnnxxMMx
Условие прекращения выполнения итераций согласно предыдущему
неравенству эквивалентно условию
...nx
.
MMxxnn)1(
1
.
...
.
2.1.11. Определение корней алгебраических уравнений
Уравнения, содержащие суммы целых степеней х, называются алгебраическими. Их
общий вид
. 0...0111......
.axaxaxannnn
Свойства алгебраических уравнений
При отыскании корней алгебраических уравнении полезно иметь в виду некоторые их
свойства:
1. Алгебраическое уравнение порядка п имеет п корней, которые могут быть
действительными или комплексными.
2. Если все коэффициенты аi, действительные, то все комплексные корни образуют
комплексно-сопряженные пары.
3. Число положительных действительных корней равно или меньше (на целое число)
числа перемен знаков в последовательности коэффициентов аi.
4. Число отрицательных действительных корней равно или меньше (на целое число)
числа перемен знаков в последовательности коэффициентов аi при замене х на -х.
Известны прямые методы отыскания корней алгебраических уравнений второй и
третьей степеней, однако для уравнений более высоких степеней приходится использовать
итерационные методы. В строго математическом смысле, найдя какой-либо корень
алгебраического уравнения х* итерационным методом, можно понизить порядок этого
уравнения, разделив его на (х—х*) и получив уравнение, порядка |п-1|. На первый взгляд
такая возможность кажется привлекательной, однако пользоваться ею следует с
осторожностью, так как даже небольшая погрешность в значении первого найденного
корня может привести к накоплению больших ошибок в значениях коэффициентов
уравнения (n-1)-й степени. Отметим, что эта процедура нередко позволяем угадать другие
корни, если несколько первых корней уже известны.
2.2. Решение систем линейных алгебраических уравнений (СЛАУ)
С этой задачей инженер, пожалуй, чаще всего сталкивается в своей практике. В
общем случае СЛАУ имеет вид
(1)
....
,...
,...
22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa
....
....
....
............
Чтобы она имела единственное решение, входящие в нее п уравнений должны быть
линейно независимыми. Необходимым и достаточным условием этого является условие
неравенства нулю определителя данной системы. Алгоритмы решения задач такого типа
подразделяются на прямые и итерационные. Возможность систематизировать прямые
методы для этой задачи делает их весьма популярными. Далее следует изложение прямых
методов (Гаусса и Жордана) и итерационных (простых итераций и Зейделя).
2.2.1. Метод исключения Гаусса
Основан на приведении системы уравнений к «треугольному» виду. При этом одно из
уравнений содержит только одну неизвестную, в каждом следующем добавляется еще по
одной неизвестной.
Применяя его, на 1-м этапе, нормируют первое уравнение, деля его коэффициенты на
a11. Затем 1-ое уравнение умножают на первые коэффициенты a i1 всех других уравнений
и последовательно вычитают из них. В результате первая переменная будет исключена из
всех уравнений, кроме первого. На 2-ом этапе нормируют 2-ое уравнение, деля его на a22,
затем 2-ое уравнение умножают на первые коэффициенты ai2 всех уравнений, начиная с 3-
го (i=3, 4, …, n), и последовательно вычитают из них. В результате вторая переменная
будет исключена из всех уравнений, кроме первого и второго. Процедура повторяют с 3-
им и последующими до (n-1)-го уравнениями, пока после n-1 этапов система не будет
приведена к треугольному виду. Математически эту процедуру можно описать
следующим образом.
На k-м этапе процесса исключения новые нормированные коэффициенты k-гo
уравнения имеют вид
(),
kkkjkjaaa..nkkj...,,1,..
а новые коэффициенты в следующих уравнениях
(, , ). (2) kjikijijaaaa....nkki...,,2,1...nkkj...,,2,1...kjki..,
После приведения системы к треугольному виду, находят xn из последнего уравнения
xn=bn/ann,
подставляют его в (n-1)-е уравнение
, 1,111,1.......nnnnnnnbxaxa
находят xn-1
1,1,111/)(.......nnnnnnnaxabx
и т.д. (для xk
), kknkjjjkkkaxabx,
1,/)(.
..
..
пока не найдут все неизвестные.
Например, при решении методом Гаусса системы уравнений
(3)
,723,922,0,24321432143214321
....
....
....
....
xxxxxxxxxxxxxxxx
после приведения их к треугольному виду, получим
,4,323,1,24434324321
.
...
...
....
xxxxxxxxxx
откуда, подставляя значение x4 в 3-е уравнение, x3 — во 2-е и т. д., находят решение
x1 = 1, x2 = 2, x3 == 3, x4 = 4.
2.2.2. Метод исключения Гаусса—Жордана
Основан на приведения системы линейных уравнений к диагональному виду. Каждое
из полученных уравнений при этом содержит одно неизвестное, что облегчает получение
решения. Его недостатком является увеличение объема вычислений.
Единственным формальным отличием этого метода от предыдущего (2) является то,
что преобразованиям на каждом этапе подвергаются все уравнения системы, а не только
уравнения, чей номер больше номера ведущего ряда i>k
(, , ). (4) ni...,,2,1.kjki..,
После преобразований сразу же получаем искомые неизвестные
xk=bk/akk () nk...,,2,1.
Применение обоих описанных методов усложняется, если какой-либо из элементов
ведущего ряда равен нулю. В последнем случае ведущий ряд нельзя нормировать. Однако,
изменив порядок, в котором расположены уравнения системы, эту трудность можно
обойти. Можно показать, что наибольшая точность достигается тогда, когда 1-й
коэффициент нормируемого уравнения имеет наибольшее значение. Поэтому строку с
нулевым или малым 1-м коэффициентом желательно заменить той из стоящих под ней
строк, в которой в том же столбце стоит коэффициент, имеющий наибольшее значение.
Хотя обычно прямые методы решения СЛАУ весьма эффективны, в случае больших
матриц они уступают итерационным методам, три из которых представлены далее: метод
простой итерации, метод Зейделя и метод последовательной верхней релаксации.
Итерационные методы применяются к системам, предварительно приведенным к виду
(5)
..
..
...1,1,111,22112323121222213132121111
.......
.....
.....
nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabax
.
.................
.
.
2.2.3. Метод простых итераций
В методе простой итерации исходные значения переменных (0-е
приближение) подставляются в правую часть системы (5) вместо , в левой
части после вычислении получаем новые значения (1-е приближение).