progonka (675832)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Магнитогорский Государственный Технический Университет имени Г.И.Носова

Кафедра математики

Реферат

Тема: Метод прогонки решения систем с трехдиагональными

матрицами коэффициентов

Выполнил: студент группы ЭА-04-2

Романенко Н.А.

Проверил: Королева В.В.

Магнитогорск 2004

Часто возникает необходимость в решении линейных алгебраических систем, матрицы которых, являясь слабо заполненными, т.е. содержащими немного ненулевых элементов, имеют определённую структуру. Среди таких систем выделим системы с матрицами ленточной структуры, в которых ненулевые элементы располагаются на главной диагонали и на нескольких побочных диагоналях. Для решения систем с ленточными матрицами коэффициентов метод Гаусса можно трансформировать в более эффективные методы.

Рассмотрим наиболее простой случай ленточных систем, к которым, как увидим впоследствии, сводится решение задач сплайн-интерполяции функций, дискретизации краевых задач для дифференциальных уравнений методами конечных разностей, конечных элементов и др. А именно, будем искать решение такой системы, каждое уравнение которой связывает три “соседних” неизвестных:

b_ix_i-1+c_ix_i+d_ix_i=r_i (1)

где i=1,2,...,n; b₁=0, d_n=0. Такие уравнения называются трехточечными разностными уравнениями второго порядка. Система (1) имеет трёхдиагональную структуру, что хорошо видно из следующего, эквивалентного (1), векторно-матричного представления:

c₁ d₁ 0 0 ... 0 0 0 x₁ r₁

b₂ c₂ d₂ 0 ... 0 0 0 x₂ r₂

0 b₃ c₃ d₃ ... 0 0 0 x₃ r₃

. . . . ... . . . * ... = ...

0 0 0 0 ... b_n-1c_n-1 d_n-1 x_n-1 r_n-1

0 0 0 0 ... 0 b_n c_n x_n r_n

Как и в решении СЛАУ методом Гаусса, цель избавится от ненулевых элементов в поддиаганальной части матрицы системы, предположим, что существуют такие наборы чисел δ_i и λ_i (i=1,2,...,n), при которых

x_i= δ_ix_i+1+ λ_i (2)

т.е. трехточечное уравнение второго порядка (1) преобразуется в двухточечное уравнение первого порядка (2). Уменьшим в связи (2) индекс на единицу и полученое выражение x_i-1= δ_i-1x_i+ λ_i-1 подставим в данное уравнение (1):

b_iδ_i-1 x_i+ b_i λ_i-1+ c_ix_i+ d_ix_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₁=0, процесс вычисления δ_i , λ_i может быть начат со значений

δ₁ = - d₁/ c₁ , λ₁ = r₁/ c₁

и продолжен далее по формулам (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₁ при 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, в силу (4), имеем:

|c₁|>|d₁|≥0

- неравенство нулю первой пары прогоночных коэффициентов, а так же

|δ₁|=|- d₁/ c₁|<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), удовлетворяющих условиям теоремы, и пусть

δ₁= - d₁/ c₁ , δ_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, где

c₁ 0 0 0 ... 0 0 0

b₂ ∆₂ 0 0 ... 0 0 0

L= 0 b₃ ∆₃ 0 ... 0 0 0

…………………………

0 0 0 0 ... b_n-1 ∆_n-1 0

0 0 0 0 ... 0 b_n ∆_n

1 -δ₁ 0 0 ... 0 0 0

0 1 δ₂ 0 ... 0 0 0

U= 0 0 1 δ₃ ... 0 0 0

…………………………

0 0 0 0 ... 0 1 -δ_n-1

0 0 0 0 ... 0 0 1

Единственное в силу утверждение теоремы LU-разложения матриц. Как видим, LU-разложение трехдиагональной матрицы А может быть выполнено очень простым алгоритмом, вычисляющем ∆_i δ_i при возрастающих значениях i. При необходимости попутно может быть вычислен

_n

det A = c₁ ∏ ∆_i .

ⁱ⁼²

В заключение этого пункта заметим, что, во-первых, имеются более слабые условия корректности и устойчивости прогонки, чем требуется в теореме условие строгого диагонального преобладания в матрице А. Во-вторых, применяется ряд других, отличных от рассмотрения нами правой прогонки, методов подобного типа, решающих как поставленную здесь задачу (1) для систем с трехдиагональными матрицами (левая прогонка, встречная прогонка, немонотонная, циклическая, ортогональная прогонки и т.д.), так и для более сложных систем с матрицами ленточной структуры или блочно-матричной структуры (например, матричная прогонка).

Список используемой литературы

В.М. Вержбитский «Численные методы. Линейная алгебра и нелинейные уравнения», Москава «Высшая школа 2000».

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов реферата