Реферат: Метод прогонки решения систем с трехдиагональными матрицами коэффициентов
👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Магнитогорский Государственный Технический Университет имени Г.И.Носова
Тема: Метод прогонки решения систем с трехдиагональными
Часто возникает необходимость в решении линейных алгебраических систем, матрицы которых, являясь слабо заполненными, т.е. содержащими немного ненулевых элементов, имеют определённую структуру. Среди таких систем выделим системы с матрицами ленточной структуры, в которых ненулевые элементы располагаются на главной диагонали и на нескольких побочных диагоналях. Для решения систем с ленточными матрицами коэффициентов метод Гаусса можно трансформировать в более эффективные методы.
Рассмотрим наиболее простой случай ленточных систем
, к которым, как увидим впоследствии, сводится решение задач сплайн-интерполяции функций, дискретизации краевых задач для дифференциальных уравнений методами конечных разностей, конечных элементов и др. А именно, будем искать решение такой системы, каждое уравнение которой связывает три “соседних” неизвестных:
b i
x i
-1
+
c i
x i
+
d i
x i
=
r i
(1)
где i
= 1,2
,..., n
; b
1
=
0 ,
d n
=
0. Такие уравнения называются трехточечными разностными уравнениями второго порядка
. Система (1) имеет трёхдиагональную структуру, что хорошо видно из следующего, эквивалентного (1), векторно-матричного представления:
0 0 0 0 ... b n
-1
c n
-1
d n
-1
x n
-1
r n-1
Как и в решении СЛАУ методом Гаусса, цель избавится от ненулевых элементов в поддиаганальной части матрицы системы, предположим, что существуют такие наборы чисел δ
i
и λ
i
(
i
=1,2
,..., n
)
, при которых
т.е. трехточечное уравнение второго порядка (1) преобразуется в двухточечное уравнение первого порядка (2). Уменьшим в связи (2) индекс на единицу и полученое выражение x i
-1
= δ
i
-1
x i
+ λ
i
-1
подставим в данное уравнение (1):
b i
δ i-1
x i
+ b i
λ
i-1
+ c i
x i
+ d i
x i+1
= r i
x i
= -
(( d i
/( c i
+ b i
δ i-1
)) x i-1
+
( r i
- b i
λ
i-1
)/( c i
- b i
δ
i-1
)).
Последнее равенство имеет вид (2) и будет точно с ним совпадать, иначе говоря, представление (2) будет иметь место, если при всех i
=1,2,…,
n
выполняются рекуррентные соотношения
δ i
= -
d i
/( c i
+ b i
δ i-1
) , λ
i
=
( r i
- b i
λ
i-1
)/( c i
- b i
δ
i-1
) (3)
Легко видеть, что, в силу условия b
1
=0
, процесс вычисления δ
i
, λ
i
может быть начат со значений
δ 1
= - d 1
/ c 1
, λ
1
=
r 1
/ c 1
и продолжен далее по формулам (3) последовательно при i
=2,3,...,
n
, причем при i
=
n
,
в силу d n
=0,
получим δ
n
=
0.Следовательно, полагая в (2) i
=
n
,будем иметь
x n
=
λ
n
=
( r n
– b n
λ
n-1
)/( c n
– b n
δ
n-1
)
(где λ
n
-1
, δ
n
-1
–
уже известные с предыдущего шага числа). Далее по формулам (2) последовательно находятся x n
-1
, x n
-2
,…, x
1
при i
=
n
-1,
n
-2,...,1
соответственно.
Таким образом, решение уравнений вида (1) описываем способом, называемым методом прогонки
, сводится к вычислениям по трём простым формулам: нахождение так называемых прогоночных коэффициентов
δ
i
, λ
i
по формулам (3) при i
=1,2,…,
n
( прямая прогонка
) и затем неизвестных x i
по формуле (2) при i
=
n
-1,
n
-2,...,1
( обратная прогонка
).
Для успешного применения метода прогонки нужно, чтобы в процессе вычислений не возникало ситуаций с делением на нуль, а при больших размерностях систем не должно быть строгого роста погрешностей округлений.
Будем называть прогонку корректной
, если знаменатели прогоночных коэффициентов
(3) не обращаются в нуль, и устойчивой
, если |δ
i
|<
1 при всех
i
€
{ 1,2,
... ,
n
}.
Приведем простые достаточные условия корректности и устойчивости прогонки, которые во многих приложениях метода автоматически выполняются.
Пусть коэффициенты
b i
и d i
уравнения
(1) при
i
=2,3,...,
n
- 1 отличны от нуля и пусть
|
c i
|>|
b i
|+|
d i
|
i
=1,2,…,
n
.
(4)
Тогда прогонка
(3), (2) корректна и устойчива (т.е. с
i
+
b i
δ i
-1
≠
0, |δ
i
|<
1).
Д о к а з а т е л ь с т в о. Воспользуемся методом математической индукции для установления обоих нужных неравенств одновременно.
- неравенство нулю первой пары прогоночных коэффициентов, а так же
Предположим, что знаменатель ( i
-1)-x прогоночных коэффициентов не равен нулю и что |δ
i
-1
|<
1. Тогда, используя свойства модулей, условия теоремы и индукционные предположения, получаем:
| с
i
+
b i
δ i
-1
|≥|
c i
| - |
b i
δ i
-1
|>|
b i
|+|
d i
| - |
bi
|*|
δi
-1
|= |
d i
|+|
bi
|
(1 - | δ i
-1
|)> |
d i
|
>0
| δ
i
|=|- d i
/
с
i
+b i
δ i-1
|=|
δ
i
|/|
с
i
+b i
δ i-1
|<
| δ
i
|/
| δ
i
|=
1
Следовательно, с
i
+
b i
δ i
-1
≠
0 и |δ
i
|<
1 при всех i
€
{ 1,2,
... ,
n
}, т.е. имеет место утверждаемая в данных условиях корректность и устойчивость прогонки. Теорема доказана.
Пусть А – матрица коэффициентов данной системы (1), удовлетворяющих условиям теоремы, и пусть
δ
1
= - d 1
/ c 1
,
δ
i
=|- d i
/ c i
+b i
δ i-1
( i=2,3,...,n
- 1
), δ
n
=0
- прогоночные коэффициенты, определяемые первой из формул (3), а
∆
i
= с
i
+
b i
δ i
-1
( i
=2,3,...,
n
)
- знаменатели этих коэффициентов (отличные от нуля согласно утверждению теоремы). Непосредственной проверкой легко убедится, что имеет место представление A
=
LU
, где
Единственное в силу утверждение теоремы LU
-разложения матриц. Как видим, LU-разложение трехдиагональной матрицы А
может быть выполнено очень простым алгоритмом, вычисляющем ∆
i
δ
i
при возрастающих значениях i
. При необходимости попутно может быть вычислен
В заключение этого пункта заметим, что, во-первых, имеются более слабые условия корректности и устойчивости прогонки, чем требуется в теореме условие строгого диагонального преобладания в матрице А
. Во-вторых, применяется ряд других, отличных от рассмотрения нами правой прогонки, методов подобного типа, решающих как поставленную здесь задачу (1) для систем с трехдиагональными матрицами (левая прогонка, встречная прогонка, немонотонная, циклическая, ортогональная прогонки и т.д.), так и для более сложных систем с матрицами ленточной структуры или блочно-матричной структуры (например, матричная прогонка).
В.М. Вержбитский «Численные методы. Линейная алгебра и нелинейные уравнения», Москава «Высшая школа 2000».
Название: Метод прогонки решения систем с трехдиагональными матрицами коэффициентов
Раздел: Рефераты по математике
Тип: реферат
Добавлен 10:04:44 12 июля 2005 Похожие работы
Просмотров: 740
Комментариев: 16
Оценило: 6 человек
Средний балл: 4.5
Оценка: 5 Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Если Вам нужна помощь с учебными работами, ну или будет нужна в будущем (курсовая, дипломная, отчет по практике, контрольная, РГР, решение задач, онлайн-помощь на экзамене или "любая другая" учебная работа...) - обращайтесь: https://clck.ru/P8YFs - (просто скопируйте этот адрес и вставьте в браузер) Сделаем все качественно и в самые короткие сроки + бесплатные доработки до самой сдачи/защиты! Предоставим все необходимые гарантии.
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Реферат: Метод прогонки решения систем с трехдиагональными матрицами коэффициентов
Сочинение На Тему Литературное Произведение
Какие Бывают Сочинения По Русскому
Реферат: Brook Taylor Essay Research Paper Brook TaylorMathematicianBiographical
Реферат: по истории. «Картофельная столица Ленинградской области»
Курсовая работа по теме Проект участка новой железнодорожной линии
Доклад по теме Вторая столица
Реферат На Тему Версии Ос Виндовс 7
Поселения и жилища
Реферат: Среднеазиатские владения Российской империи
Реферат: Понятие и состав национального богатства в зарубежных странах
Реферат: Вплив житлових умов на здоров я та побут населення Гігієнічні вимоги до життя об рунтування но
Курсовая Работа На Тему Наследственные Права В Международном Частном Праве
Реферат: Обеспечение безопасности жизнедеятельности работающих в механическом цехе 2
Прекращение Уголовного Дела Реферат
Дипломная работа по теме Водоотведение агрогородка с заводом по производству кваса
Реферат На Тему Недостаточность Надпочечников И Надпочечниковый Криз
Сочинение Про Ивана 3
Дипломная работа по теме Автоматизация рабочего места менеджера в салоне красоты
Дипломная работа по теме Проектирование двухквартирного жилого дома
Доклад по теме Этическое измерение глобально-космических проектов
Реферат: Паблик релейшенс (pr) как одна из реалий сегодняшнего дня. История, психология и формы деятельности pr сотрудника
Сочинение: Роман Н.Г. Чернышевского "Что делать?" о человеческих отношениях
Доклад: Гражданская война в России