Метод прогонки icon

Метод прогонки



НазваниеМетод прогонки
Дата конвертации09.09.2012
Размер38.04 Kb.
ТипДокументы

МЕТОД ПРОГОНКИ.


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



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

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



Для численного решения систем трехдиагональными матрицами применяется метод прогонки, который представляет собой вариант метода последовательного исключения неизвестных.

Т.е. матрицу А можно записать



  1. Идея метода прогонки состоит в следующем. Решение системы (1) ищется в виде



где -неизвестные коэффициенты, которые последовательно находятся от до (прямая прогонка ), а затем последовательно вычисляются (обратная прогонка) .

Выведем формулы для вычисления Из (3) можно получить



Подставляя имеющиеся выражения для в уравнение (1),приходим при к уравнению Последнее уравнение будет выполнено если коэффициенты выбрать такими, чтобы выражения в квадратных скобках обращались в нуль.

А именно, достаточно положить gif" name="object19" align=absmiddle width=322 height=45>Для отыскания всех достаточно задать

Эти начальные значения находим из требования эквивалентности условия (3) при т.е. условия , первому из уравнений (2).

Таким образом, получаем

(5)

Нахождение коэффициентов по формулам (4), (5) называется прямой прогонкой. После того, как прогоночные коэффициенты найдены, решение системи (1), (2) находится по рекуррентной формуле (3), начиная с Для начала счета по этой формуле требуется знать , которое определяется из уравнений



И равно

.

Нахождение по формулам

(6)

называется обратной прогонкой. Алгоритм решения системы (1), (2) определяемый формулами (4)-(6) называется методом прогонки.

Метод прогонки можно пременять, если знаменатели выражений (4), (6) не обрщаются в нуль.

Покажем, что для возможности применения метод прогонки достаточно потребовать, чтобы коэффициенты системы (1), (2) удовлетворяли условиям

(8)


Сначала докажем по индукции, что при условиях (7), (8) модули прогоночных коэффициентов не превосходят единицы. Согласно (5), (8) имеем . Предположим,что для некоторого и докажем, что

Прежде всего для любых двух комплексных чисел и докажем неравенство



Из неравенства треугольника имеем



Откуда



Вернемся теперь к доказательству , если . Согласно имеем оценку



а, используя (7) , получаем



т.е. знаменатели выражений (4) не обращаются в нуль.

Более того



Следовательно,

Далее, учитывая второе из условий (8) и только что доказанное неравенство , имеем



т.е. не обращается в нуль и знаменатель в выражении для .

К аналогичному выводу можно прийти и в том случае, когда условия (7), (8) заменяются условиями

Таким образом при выполнении условий (7), (8) (так же как и условий (9), (10)) система (1), (2) эквивалентна системе (4)-(6). Поэтому эти условия гарантируют существование и единственность решения системы (1), (2) и возможность нахождения этого решения методом прогонки.

Кроме того, доказанные неравенства , обеспечивают устойчивость счета по рекуррентным формулам (6). Последнее означает, что погрешность,внесенная на каком-либо шаге вычислений, не будет возрастать при переходе к следующим шагам.

Действительно, пусть в формуле (6) при вместо вычислена величина

Тогда на следующем шаге вычислений, т.е. при

вместо

получим величину и погрешность окажется равной



Отсюда получаем, что ,т.е. погрешность не возрастает.

Подсчитаем число арифметических действий, выполняемых при решении задачи (1), (2) методом прогонки.

По формулам (4), что реализуемые с помощью шести арифметических действий, вычисления производятся раз, по формуле (6) выполняется 5 арифметических действий, наконец по формуле (3), требующей всего два действия, вычисления осуществляются раз. Итак в методе прогонки всего затрачивается



арифметических действий, т.е. число действий растет линейно относительно числа неизвестных

При решении же произвольной системы линейных алгебраических уравнений методом Гаусcа число действий пропорционально кубу числа неизвестных.




Похожие:

Метод прогонки iconМетод прогонки решения систем с трехдиагональными
Среди таких систем выделим системы с матрицами ленточной структуры, в которых ненулевые элементы располагаются на главной диагонали...
Метод прогонки iconТема: «счастье это когда тебя понимают»: так ли это?
Основные методы и приемы: метод наблюдения, словесный метод, игровой метод, метод «вопроса в связи с обстоятельствами»
Метод прогонки iconПрибыль и ее роль в рыночной экономике Содержание
Метод прямого счета, аналитический метод и метод совмещенного расчета
Метод прогонки iconПрограмма составлена кандидатом физ мат наук В. А. Зайцевым
Автоколебания. Метод точечных преобразований. Системы с переменной структурой. Приближенное исследование автоколебаний. Метод эквивалентной...
Метод прогонки iconФедеральное агентство по образованию Государственное образовательное учреждение
Вычислить определитель 3-го порядка, используя метод Саррюса (или метод треугольников) и метод разложения по минорам какого-нибудь...
Метод прогонки iconЗвіт до лабораторної роботи №3 з курсу “Комп’ютерні методи дослідження інформаційних процесів та систем” на тему
До ітераційних методів належать: метод простої ітерації, метод Зейделя, метод верхньої релаксації та інші
Метод прогонки icon6 Метод Рунге-Кутта 2-ого порядка (модифицированный метод Эйлера)
В правой части полагаем, как в исходном методе Эйлера. Получаем явный метод, для которого погрешность
Метод прогонки iconЧто такое метод проектов
Метод проектов (от греческого путь исследования). Метод проектов это модель обучения, которая вовлекает ученика в процесс решения...
Метод прогонки iconМетоды беседы в психологии. Метод беседы
Метод беседы — психологический вербально-коммуникативный метод, заключающийся в ведении тематически направленного диалога между психологом...
Метод прогонки iconРеферат з математики
Одним з найпоширеніших методів розв'язування систем лінійних рівнянь є метод послідовного виключення невідомих, або метод Гаус­са....
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы