Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

Некоторые дополнительные вычислительные методы



 Другие рефераты
Некоторые Теоремы Штурма Некоторые вопросы анализа деловых проблем Некоторые подходы к задачам распознавания и их приложениям Нестандартный анализ

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) в
нескольких точках отрезка восстановить ее значения в остальных точках
данного отрезка. Разумеется, такая постановка задачи допускает сколь угодно
1234
скачать работу


 Другие рефераты
Пути повышения эффективности образования
Образование 19в в Казани
Жүрек
Советский период истории государства и права России


 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ