Материалы сайта
Это интересно
Численные методы
МЕТОД ПРОГОНКИ. Система уравнений для определения коэффициентов сплайна представляет собой частный случай систем линейных алгебраических уравнений [pic] с трехдиагональной матрицей [pic], т.е. с матрицей, все элементы которой,не лежащие на главной и двух побочных диагоналях, равны нулю [pic] при [pic] та [pic] В общем случае системы линейных алгебраических уравнений с трехдиагональной матрицей имеют вид [pic] Для численного решения систем трехдиагональными матрицами применяется метод прогонки, который представляет собой вариант метода последовательного исключения неизвестных. Т.е. матрицу А можно записать [pic] 1) Идея метода прогонки состоит в следующем. Решение системы (1) ищется в виде [pic] где [pic]-неизвестные коэффициенты, которые последовательно находятся от [pic] до [pic] (прямая прогонка ), а затем последовательно вычисляются [pic] (обратная прогонка) . Выведем формулы для вычисления [pic] Из (3) можно получить [pic] Подставляя имеющиеся выражения для [pic] в уравнение (1),приходим при [pic] к уравнению [pic] Последнее уравнение будет выполнено если коэффициенты [pic] выбрать такими, чтобы выражения в квадратных скобках обращались в нуль. А именно, достаточно положить [pic]Для отыскания всех [pic] достаточно задать [pic] Эти начальные значения находим из требования эквивалентности условия (3) при [pic] т.е. условия [pic] , первому из уравнений (2). Таким образом, получаем [pic] (5) Нахождение коэффициентов [pic] по формулам (4), (5) называется прямой прогонкой. После того, как прогоночные коэффициенты [pic] найдены, решение системи (1), (2) находится по рекуррентной формуле (3), начиная с [pic] Для начала счета по этой формуле требуется знать [pic] , которое определяется из уравнений [pic] И равно [pic]. Нахождение [pic] по формулам [pic] (6) называется обратной прогонкой. Алгоритм решения системы (1), (2) определяемый формулами (4)-(6) называется методом прогонки. Метод прогонки можно пременять, если знаменатели выражений (4), (6) не обрщаются в нуль. Покажем, что для возможности применения метод прогонки достаточно потребовать, чтобы коэффициенты системы (1), (2) удовлетворяли условиям [pic] (8) Сначала докажем по индукции, что при условиях (7), (8) модули прогоночных коэффициентов [pic] не превосходят единицы. Согласно (5), (8) имеем [pic]. Предположим,что [pic] для некоторого[pic] и докажем, что [pic] Прежде всего для любых двух комплексных чисел [pic] и [pic] докажем неравенство [pic] Из неравенства треугольника имеем [pic] Откуда [pic] Вернемся теперь к доказательству [pic], если [pic]. Согласно имеем оценку [pic] а, используя (7) , получаем [pic][pic][pic] т.е. знаменатели выражений (4) не обращаются в нуль. Более того [pic] Следовательно, [pic] Далее, учитывая второе из условий (8) и только что доказанное неравенство [pic], имеем [pic] т.е. не обращается в нуль и знаменатель в выражении для [pic]. К аналогичному выводу можно прийти и в том случае, когда условия (7), (8) заменяются условиями [pic] Таким образом при выполнении условий (7), (8) (так же как и условий (9), (10)) система (1), (2) эквивалентна системе (4)-(6). Поэтому эти условия гарантируют существование и единственность решения системы (1), (2) и возможность нахождения этого решения методом прогонки. Кроме того, доказанные неравенства [pic], [pic] обеспечивают устойчивость счета по рекуррентным формулам (6). Последнее означает, что погрешность,внесенная на каком-либо шаге вычислений, не будет возрастать при переходе к следующим шагам. Действительно, пусть в формуле (6) при [pic] вместо [pic] вычислена величина [pic] Тогда на следующем шаге вычислений, т.е. при [pic] вместо [pic] получим величину [pic] и погрешность окажется равной [pic] Отсюда получаем, что [pic],т.е. погрешность не возрастает. Подсчитаем число арифметических действий, выполняемых при решении задачи (1), (2) методом прогонки. По формулам (4), что реализуемые с помощью шести арифметических действий, вычисления производятся [pic] раз, по формуле (6) выполняется 5 арифметических действий, наконец по формуле (3), требующей всего два действия, вычисления осуществляются [pic]раз. Итак в методе прогонки всего затрачивается [pic] арифметических действий, т.е. число действий растет линейно относительно числа неизвестных [pic] При решении же произвольной системы линейных алгебраических уравнений методом Гаусcа число действий пропорционально кубу числа неизвестных.
1 2 3 4 5 6 7 8 9 10 11 12 13 14