Итерационные методы решения линейных систем и задач на собственные значения

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

Белгородский государственный национальный исследовательский университет

НИУ «БелГУ»

Факультет математики и информационных технологий

Кафедра алгебры, теории чисел и геометрии

Курсовая работа

Итерационные методы решения линейных систем и задач на собственные значения

Студентки 3 курса группы 010806

Селезнёвой Татьяны Олеговны

Научный руководитель: к. ф.-м. н.

доцент А.Г. Сокольский

Белгород, 2011



Содержание

Введение

1. Основные понятия

2. Метод простой итерации (метод Якоби)

3. Общий неявный метод простой итерации

4. Модифицированный метод простой итерации

5. Метод Гаусса-Зейделя

6. Метод верхней релаксации

7. Итерационный метод П.Л. Чебышева

8. Решение полной проблемы собственных значений. Метод вращений

9. Применение итерационных методов

Заключение

Библиографический список

Введение

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

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

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



1. Основные понятия

Системой линейных алгебраических уравнений (далее СЛАУ), содержащей m уравнений и n неизвестных, называется система вида:

,

Здесь x₁, x₂, …, x_n -- неизвестные, которые надо определить. a₁₁, a₁₂, …, a_mn -- коэффициенты системы -- и f₁, f₂, … f_m -- свободные члены -- предполагаются известными. Индексы коэффициентов (a_ij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

Такую систему удобно записывать в матричном виде:

A•X=F (1.1)

Понимая под А основную матрицу системы

А под X и F вектор-столбцы вида

,

Первый из которых подлежит определению, а второй задан.

2. Метод простых итераций (метод Якоби)

Рассмотрим квадратную систему линейных уравнений с вещественными коэффициентами, которую запишем в матричном виде (1.1).

Предполагая однозначную разрешимость системы (1.1), заменим матричное уравнение эквивалентным ему уравнением:

,(2.1)

где ф - вещественное число, называемое стационарным параметром. С помощью (2.1) составим итерационную последовательность векторов , определив её рекуррентно:

(k = 0,1,2,…..) (2.2)

при произвольном выборе нулевого приближения.

Таким образом, метод простой итерации сводится к замене точного решения системы (1.1) k - ой итерацией с достаточно большим номером k.

Графически метод Якоби можно представить следующим образом:

Оценим погрешность метода простой итерации. Очевидно, что

,(2.3)

где Е - единичная матрица

Рис. 1. Схема выполнения метода Якоби

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

.(2.4)

Из (2.4) вытекает неравенство, справедливое для любой матрицы и любого вектора :

.(2.5)

Из матричного уравнения погрешности (2.3) и неравенства (2.5) получаем, что для любого номера :

.(2.6)

Теорема 2.1. Для того, чтобы итерационная последовательность (2.2) при любом выборе начального приближения и при данном значении параметра сходилась к точному решению системы (1.2), достаточно, чтобы было выполнено условие

.(2.7)

При этом итерационная последовательность сходится со скоростью геометрической последовательности со знаменателем .

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

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

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

.(2.8)

Из (2.6) и Теоремы 2.1 следует, что , и (2.8) выполняется при условии , т.е при . Отсюда видно, что для уменьшения числа итераций , достаточных для достижения заданной - точности, следует выбрать параметр так, чтобы получить минимум функции .

Считая матрицу симметричной и положительно определенной, мы приходим к следующей задачей оптимизации: найти минимум функции

.

3. Общий неявный метод простой итерации

Рассмотренный в предыдущем пункте метод Якоби получается из неявного метода в частном случае с заменой матрицы В единичной матрицей Е(nЧn)

Неявный метод простой итерации заключается в замене итерационной последовательности (1.1) более общей последовательностью, определяемой соотношением:

(3.1)

Где матрица В представляет собой некоторую «легкообратимую» квадратную матрицу порядка n, а ж - стационарный параметр.

Теорема 3.1 (Теорема А.А. Самарского). Пусть матрица является симметричной и положительно определенной, а матрица положительно определенной. Тогда для того, чтобы итерационная последовательность



(3.2)

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

(3.3)

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

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

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

С помощью последнего равенства легко проверяется справедливость для введенного нами скалярного произведения четырех аксиом скалярного произведения.

Далее естественно ввести «энергетическую норму» вектора , положив ее равной . Эту энергетическую норму обозначим как .

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

.(3.4)

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

Теорема 3.2. Пусть матрица и симметричны и положительно определены, - погрешность общего неявного метода простой итерации. Тогда для того, чтобы при было справедливо неравенство

,

необходимо и достаточно, чтобы было выполнено следующее условие

(3.5)

Применим Теорему 3.2. для нахождения значения стационарного параметра , при котором скорость сходимости будет максимальной. Как уже было сказано выше, для этого необходимо найти минимум функции

Так как обе матрицы и являются симметричными и положительно определенными, то существуют такие постоянные и , что справедливы неравенства . Будем считать, что постоянные и в этих неравенствах нам заданы. Сопоставляя это неравенство с условием (3.5), мы получим, что минимальное значение достигается при условии

,

откуда получаем, что оптимальное значение параметра и минимальное значение .

4. Модифицированный метод простой итерации

Модифицированный метод получается из общего неявного метода простой итерации при следующих условиях:

ж=1, ,

тогда получаем:

D(X_k+1-X_k)+AX_k=F



При этом матрица А - симметричная, все её диагональные элементы - положительны)

Из теоремы Самарского вытекает, что для сходимости модифицированного метода простой итерации можно записать в форме:

,

Так как , то достаточное условие сходимости можно переписать в эквивалентном виде:

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

, (для i=1,2,…,n)

, (для j=1,2,…,n)

итерация линейный алгебраический вещественный

5. Метод Гаусса-Зейделя

Рассмотрим еще один итерационный метод решения систем линейных алгебраических уравнений. Метод Гаусса-Зейделя заключается в последовательном выражении неизвестных. Этот метод является одним из самых распространенных и наиболее легко программируемых.

Пусть задана СЛАУ

(5.1)

Предположим, что диагональные элементы не нулевые (в противном случае можно переставить уравнения). Выразим неизвестные из каждого уравнения:

(5.2)

Зададим некоторые начальные (нулевые) приближения значений неизвестных: , подставляя эти приближения в первое уравнение системы (5.2) , получим новое (первое) приближение для

Используя это значение и нулевые приближения для других неизвестных получим новое приближение для и т.д. до .

На этом заканчивается первая итерация решения системы. Используя теперь полученные приближения таким же образом проводи вторую итерацию.

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

Для сходимости итерационного процесса достаточно, чтобы модули диагональных коэффициентов для каждого уравнения системы были не меньше сумм модулей всех остальных коэффициентов (преобладание диагональных коэффициентов):

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

Графически метод Зейделя можно представить следующим образом:

Рис. 2. Схема выполнения метода Гаусса-Зейделя

6. Метод верхней релаксации

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

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

Метод верхней релаксации является обобщением метода Зейделя. В координатной форме метод верхней релаксации имеет следующий вид

,

При этот метод совпадает с методом Зейделя.

В методе верхней релаксации параметр щ выбран так, чтобы являлось наименьшим наибольшее по модулю собственное значение матрицы E-щ(D+щL)^-1A? Осуществляющей переход от k-oй итерации к (k+1)-й.

Если матрица А является симметричной и положительно определенной, то для сходимости метода верхней релаксации достаточно, чтобы было выполнено условие 0<щ<2

7. Итерационный метод П.Л. Чебышева

Итерационный метод П.Л. Чебышева подразумевает под собой рассмотрение более общего случая при решении СЛАУ, когда в указанном методе значения итерационного параметра ж зависят от номера k итерации. В таком случае последовательность итераций будет определяться соотношением:



Найдутся такие г₁ и г₂ такие, что: г₁В?А?г₂В

Будем считать, что г₁ и г₂ заданы и равны соответственно наибольшему и наименьшему собственным значениям АХ=лВХ.

Оценим

Сделаем замену: Z_k=B^-1/2•V_k

Соотношение погрешности при такой замене будет иметь вид:

V_k+1=(E-ж_k+1C)•V_k (k=0,1,2,..), где С=В^-1/2•A•B^-1/2

Оценим :

Тогда из равенства

= => <q_k,

Где q_k=

Отсюда получаем, что итерационный процесс П.Л.Чебышева сходится при условии, что последовательность { q_k }>0

Поскольку каждое значение q_k является функцией параметров ж₁, ж₂, …, ж_k возникает задача построения оптимального набора итерационных параметров из условия минимума q_k для фиксированного k.

Поскольку все л_s лежат на отрезке [г₁, г₂], то расширяя область, по которой берется максимум, мы получим:

Полученная задача имеет более простое решение.

Положим P(t)= и P(0)=1.

Сделаем замену:

,

Где

Используем полином Чебышева

P_k(S)=T_k(S)•[T_k(S₀)]^-1, где

.

Так как max_|S|?1|T_k(S)|=1, то



Исходя из равенства

И приравнивая корни полиномов, стоящих в правой и левой части этого равенства, получим оптимальные значения итерационных параметров:

Итерационный процесс с указанным оптимальным набором параметров называется чебышевским.

Теорема 7.1. Если матрицы А и В симметричны и положительно определены и если г₁В?А?г₂В, то чебышевский итерационный процесс сходится и для погрешности Z_k после выполнения k итераций справедлива оценка:

<q_k, где

8. Решение полной проблемы собственных значений. Метод вращений

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

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

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

D=T'AT, (8.1)

где D - диагональная матрица.

Замечание: При ортогональном преобразовании матрицы А сферическая норма этой матрицы не изменяется, следовательно от всех преобразований преобразование (8.1) отличается тем, что делает максимальной сумму квадратов диагональных элементов преобразованной матрицы и минимальной - сумму квадратов всех внедиагональных элементов.

Методом вращения называется итерационный метод, при котором матрица Т находится как предел бесконечного произведения элементарных матриц вращения, каждая из которых имеет вид:

(8.2)

В целом метод вращений состоит в построении последовательности матриц А₁, А₂, …, A_v, A_v+1, …, каждая последующая из которых получается из предыдущей при помощи элементарного шага вида A_v+1=T'_ijA_vT_ij.

Рассмотрим один такой шаг, осуществляемый матрицей (8.1)

(8.3)

Из соотношений (8.3) и из условия симметричности матрицы А вытекает следующее равенство:

(8.4)

Из равенства (8.4) вытекает, что для максимального уменьшения суммы квадратов всех внедиагональныхэлементов необходимо матрицу (8.2) выбрать так, чтобы выполнялось:

1) ,

2) (8.5)

Таким образом, метод вращений состоит в построении последовательности матриц, каждая следующая из которых получается из предыдущей посредством ортогональных преобразований A_v+1=T'_ijA_vT_ij, в которых T_ij выбирается так, чтобы были выполнены равенства (8.5)

Метод вращений сходится.

9. Применение итерационных методов

Покажем применение итерационных методов на конкретном примере.

Пример 1. Решение системы линейных уравнений методом Якоби.

Пусть дана система уравнений:

Требуется найти решение системы с точностью

Приведем систему к виду удобному для итерации:

Выберем начальное приближение, например

- вектор правой части.

Тогда первая итерация получается так:

Аналогично получаются следующие приближения к решению.

, ,

Найдем норму матрицы В. Будем использовать норму

Так как сумма модулей элементов в каждой строке равна 0.2, то = 0.2 < 1/2, поэтому критерий окончания итераций в этой задаче

Вычислим нормы разностей векторов:

,

Так как заданная точность достигнута на четвертой итерации.

Ответ: x ₁ = 1.102, x ₂ = 0.991, x ₃ = 1.101

Пример 2. Решение систем линейных уравнений методом Зейделя.

Рассмотрим параллельно решение 3-х систем уравнений:

, ,

Приведем системы к виду удобному для итераций:



, ,

Заметим, что условие сходимости выполнено только для первой системы. Вычислим 3 первых приближения к решению в каждом случае.

1-ая система.

, , ,

Точное решение здесь x ₁ = 1.4, x ₂ = 0.2. Итерационный процесс сходится.

2-ая система.

, , ,

итерационный процесс разошелся. Точное решение x ₁ = 1, x ₂ = 0.2.

3-я система.

, , ,

итерационный процесс зациклился.

Точное решение x ₁ = 1, x ₁ = 2.



Заключение

Итерационные методы решения СЛАУ используются для решения СЛАУ большой размерности с разреженными матрицами, а также для уточнения решения СЛАУ, полученного с помощью любого прямого метода. Формулировка и применение итерационных методов требует определенных знаний и определенного опыта. Выбор эффективного итерационного метода решения конкретной задачи существенно зависит от ее характерных свойств. Поэтому никаких общих правил выбора наилучшего итерационного метода решения не существует.

Оптимальным же является комплексное применение методов решения СЛАУ, т.е. получение приближенного решения с помощью прямого метода и последующего уточнения решения с помощью итерационных методов.

Библиографический список

1. Турчак Л.И., Плотников П.В. Основы численных методов: Учебное пособие. - 2-е изд., перераб. и доп. - М.:ФИЗМАТЛИТ, 2003. - 304 с.

2. Бояршинов М.Г. Численные методы. Часть 1: Учебное пособие для студентов направления «Прикладная математика и информатика». - Перм. Гос. Техн. Ун-т. Пермь, 1998. - 176 с.

3. Ильин В.А., Позняк Э.Г. Линейная алгебра: Учеб. Для Вузов. - 5-3 изд. - М.:ФИЗМАТЛИТ, 2002. - 320 с.

4. Самарский А.А., Гулин А.В. Численные методы: Учеб. Пособие для вузов. - М.: Наука. Гл. ред физ.-мат. Лит-ры, 1989. - 432 с.

5. Калиткин Н.Н. Численные методы. - М.: Наука. Гл. ред. физ.-мат. Лит-ры, 1978. - 512с.

6. Масловская Л.В., Масловская О.М. Численные методы: Учеб.пособие - Одесса, Укрполиграф, 2006. - 146 с.

7. Письменный Д.Т. Конспект лекций по высшей математике. 1часть. -5 изд. - М,: Айрис-пресс, 2005. - 288 с.

8. Канатников А.Н., Крищенко А.П. Линейная алгебра. 3-е изд., стер. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002 -- 336 с. (Сер. Математика в техническом университете. Вып. IV)

Размещено на Allbest.ru

...