Некоторые дополнительные вычислительные методы
Другие рефераты
1. Решение систем линейных уравнений
Системы линейных уравнений (СЛУ) имеют в вычислениях очень большое
значение, так как к ним может быть приведено приближенное решение широкого
круга задач. Так, основными источниками возникновения СЛУ являются теория
электрических цепей, уравнения балансов и сохранения в механике, гидравлике
и т.д. Существует несколько способов решения таких систем, которые в
основном делятся на два типа: 1) точные методы, представляющие собой
конечные алгоритмы для вычисления корней системы, 2) итерационные методы,
позволяющие получать корни системы с заданной точностью путем сходящихся
бесконечных процессов. Заметим, что даже результаты точных методов являются
приближенными из-за неизбежных округлений. Для итерационных процессов также
добавляется погрешность метода.
Пример системы линейных уравнений: [pic]
Или в матричном виде: [pic],
где [pic]матрица коэффициентов системы;
[pic] - вектор неизвестных; [pic] - вектор свободных членов.
Схема Халецкого
Запишем систему линейных уравнений в матричном виде: [pic],
где A=[aij] – квадратная матрица порядка n и
[pic], [pic] - векторы-столбцы.
Представим матрицу A в виде произведения нижней треугольной матрицы B=[bij]
и верхней треугольной матрицы C=[cij] с единичной диагональю [pic], где
[pic] и [pic].
Тогда элементы bij и cij определяются по формулам
[pic] и [pic]
Отсюда искомый вектор x может быть вычислен из уравнений [pic] и [pic].
Так как матрицы B и C – треугольные, то системы легко решаются:
[pic] и [pic]
Из этих двух формул видно, что числа yi выгодно вычислять вместе с
коэффициентами cij. Этот метод получил название схемы Халецкого. В схеме
применяется обычный контроль с помощью сумм. Если матрица A –
симметрическая aij=aji, то [pic]
Пример. Решить систему [pic]
Решение.
В первый раздел таблицы впишем матрицу коэффициентов системы, ее свободные
члены и контрольные суммы. Далее так как [pic] [pic], то первый столбец из
раздела 1 переносится в первый столбец раздела II. Чтобы получить первую
строку раздела II, делим все элементы первой строки раздела I на
элемент[pic], в нашем случае на 3.
Имеем: [pic]; [pic]; [pic]; [pic]; [pic].
Переходим к заполнению второго столбца раздела II, начиная со второй
строки. Пользуясь формулами, определяем [pic]: [pic]; [pic]; [pic].
Далее определяя по формулам, заполняем вторую сетку для раздела II:
[pic][pic]
[pic]
[pic]
Затем переходим к третьему столбцу, вычисляя его элементы [pic] и [pic] по
формулам и т.д., пока не будет заполнена вся таблица раздела II. Таким
образом, заполнение раздела II происходит способом “елочки”: столбец -
строка, столбец - строка и т.д.
В разделе Ш, пользуясь формулами, определяем [pic] и [pic].
Текущий контроль осуществляется с помощью столбца S, над которым
производятся те же действия, что и над столбцом свободных членов.
|0 |1,200|0,000|0,000|
| |0 |0 |0 |
|1 |1,200|1 |0,948|
| |0 |,0600|0 |
|2 |0,999|1,005|0,999|
| |2 |4 |1 |
|3 |0,999|1.000|1,000|
| |6 |1 |1 |
|4 |1 |1,000|1,000|
| |,0000|0 |0 |
|5 |1 |1,000|1,000|
| |,0000|0 |0 |
Точные значения корней: [pic].
2. Методы решения нелинейных уравнений
Как известно, далеко не всякое уравнение f(x)=0 можно решить точно, т.е. не
всегда можно найти число [pic] такое что f([pic])?0. В первую очередь это
относится к трансцендентным уравнениям. Кроме того, даже для алгебраических
уравнений степени выше четвертой не существуют формулы, выражающей их
решения через коэффициенты уравнения при помощи арифметических операций и
извлечение корней. Для уравнений третьей и четвертой степени формулы для
отыскания корней существуют, но они настолько сложны, что практически не
применяются. Поэтому большое значение имеет приближенное вычисление корней
уравнения f(x)=0. Для этого существует множество методов некоторые, из
которых мы рассмотрим.
Метод хорд
Пусть дано уравнение f(x)=0, где функция f(x) определена и непрерывна на
интервале
[a, b] и f(a)f(b)<0. Пусть для определенности f(a)<0 и f(b)>0. Разделим
отрезок [a, b] в отношении - f(a):f(b). Это даст нам приближенное значение
корня x1 = a + h1, где
[pic].
Далее этот прием применяем к одному из отрезков [a, x1] или [x1, b], на
концах которого функция f(x) имеет противоположные знаки. Аналогично
находим второе приближение x2 и т.д. Геометрически этот способ эквивалентен
замене кривой y = f(x) хордой, проходящей через точки А[a, f(a)] и B[b,
f(b)].
f(b)
f(a)
? x3 x2 x1 b=x0 a=x0 x1 x2
b
a
f(b)
Действительно, уравнение хорды АВ имеет вид [pic]
При х = х1 и y = 0, получим [pic]
Полагая, что на отрезке [a, b] вторая производная f''(x) сохраняет
постоянный знак, метод хорд сводится к двум различным вариантам.
Из рис. 1 видно, что конец а неподвижен и последовательные приближения:
x0=b;
[pic]
образуют ограниченную монотонно убывающую последовательность, причем
a0.
Пример. Вычислить методом Ньютона отрицательный корень уравнения
[pic] с пятью верными знаками.
Решение. Полагая в левой части уравнение [pic] получим [pic].
Следовательно, искомый корень [pic] находится в интервале [pic]. Сузим
найденный интервал. Так как [pic] то [pic]. В этом последнем интервале
[pic] и [pic].Так как [pic] и [pic], то можем принять за начальное
приближение [pic]. Последовательные приближения [pic] вычисляем по
следующей схеме:
|[pi|[pic] |[pic] |[pic] |[pic] |
|c] | | | | |
|0 |-11 |3453 |-5183 |0,7 |
|1 |-10,3 |134,3 |-4234 |0,03 |
|2 |-10,27 |37,8 |-4196 |0,009 |
|3 |-10,261|0,2 |- |- |
Останавливаясь на [pic], проверяем знак значения [pic]. Так как [pic], то,
[pic] и любое из этих чисел дает искомое приближение.
Метод итерации
Заменим уравнение f(x)=0 эквивалентным x=?(x). Выберем некоторое начальное
приближение x0 и вычислим дальнейшие приближения по формулам x1= ?(x0), x2=
?(x1), …, xn= ?(xn-1). Если последовательность xn имеет предел, то
итерационный процесс
xn= ?(xn-1) (n=1, 2, …) называется сходящимся. Пусть функция ?(x)
непрерывна. Переходя к пределу в равенстве xn= ?(xn-1), получим
[pic] Следовательно, [pic] является корнем уравнения x=?(x) и может быть
вычислен по формуле xn= ?(xn-1) (n=1, 2, …) с любой точностью. Для
данного метода существуют две теоремы:
Теорема 1. Пусть корень [pic] уравнения x=?(x), а также его
последовательные приближения x0, xn= ?(xn-1) (n=1, 2, …) содержатся в
интервале [a, b] и [pic] на [a, b]. Тогда справедливы утверждения:
1. итерационный процесс xn= ?(xn-1) сходится к корню уравнения [pic];
2. [pic];
3. [pic].
Следствие 1. Если требуется найти корень с точностью ?, то кончаем
итерационный процесс тогда, когда [pic]0 на
(a, b), то последовательные приближения xn= ?(xn-1) (n=1, 2, …) сходятся
к корню монотонно; если ?'(x)<0 на (a, b), то последовательные приближения
колеблются около корня.
Теорема 2. Если [pic] на [a, b], а корень [pic] и начальное приближение x0
находятся на более узком отрезке [?, ?], где [pic], то справедливы
заключения теоремы 1.
Привести уравнение f(x)=0 к виду x=?(x) таким образом, чтобы получить
сходящийся итерационный процесс, можно различными способами. Рассмотрим два
из них:
1) уравнение f(x)=0 равносильно при ??0 уравнению ?f(x)=0 и уравнению x=
?f(x)+x. Обозначим ?f(x)+x через ?(x), получим x= ?(x). Параметр ? подберем
так, чтобы функция ?'(x)= ?f'(x)+1 на [a, b] была по модулю меньше единицы.
2) если [pic], то итерационный процесс расходится. Заменим уравнение x=?(x)
эквивалентным ему уравнением x=?(x), где ?(x) – функция, обратная функции
?(x). Так как [pic], то итерационный процесс xn=?(xn-1) будет сходящимся.
Пример. Методом итерации найти корень уравнения 5x-8lnx=8 с точностью 0,01.
Решение. Запишем уравнение в виде [pic] и построим соответствующие графики:
[pic]
Уравнение имеет два корня: [pic]. За начальные приближения возьмем z0=0,5 и
x0=3,5. Для уточнения запишем [pic]. Здесь
[pic] Следовательно, итерационный процесс сходится. Погрешность оценим по
формуле [pic] [pic], результаты вычислений приведены в таблице:
| n| x|1+lnx|[pic] |[pic] |
| 0 |3,5 |2,253| 3,605| |
|1 |3,60| | |------ |
|2 |5 |2,282|3,651 |0,105 |
|3 |3,65| |3,672 |0,046 |
|4 |1 |2,295|3,682 |0,021 |
| |3,67| | |0,010 |
| |2 |2,301| | |
| |3,68| | | |
| |2 | | | |
Так как ?’(z0)?3>1, то итерационный процесс расходится. Найдем функцию
[pic], обратную функции ?(x). Так как [pic], то итерационный процесс [pic]
будет сходится. [pic], результаты вычислений приведены в таблице:
| n| |[pic] |[pic] |[pic] |
| |zn | | | |
| 0 |0,5 | | 0,503 | |
|1 |0,50|-0,688 |0,504 |------ |
|2 |3 |-0,686 |------ |0,0015 |
| |0,50|------ | |0,0005 |
| |3 | | | |
3. Интерполирование и экстраполирование
Задача интерполирования состоит в том, чтобы по значениям функции f(x) в
нескольких точках отрезка восстановить ее значения в остальных точках
данного отрезка. Разумеется, такая постановка задачи допускает сколь угодно
| |  скачать работу |
Другие рефераты
| 
