Xreferat.com » Рефераты по математике » Метод релаксации переменных решения СЛАУ

Метод релаксации переменных решения СЛАУ

Размещено на /

ВВЕДЕНИЕ


Численное решение СЛАУ – одна из наиболее часто встречающихся задач в научно-технических исследованиях. Такая задача возникает в математической физике (численное решение дифференциальных и интегральных уравнений), экономике, статистике. При этом прикладные задачи часто требуют решения больших и сверхбольших СЛАУ с числом неизвестных более 1000. К таким СЛАУ, например, приводит численное решение двумерных и особенно трехмерных задач математической физики, в которых условия физической и геометрической аппроксимации двумерной и трехмерной области диктуют использование достаточно мелкой расчетной сетки с большим числом расчетных узлов по линейному размеру.

Существующие библиотеки программ на языках высокого уровня, разработаны на основе, так называемых, прямых методов решения СЛАУ, типа метода Гаусса и его модификаций. Число арифметических операций умножения для численного решения СЛАУ размерностью Метод релаксации переменных решения СЛАУ с помощью прямого метода - Метод релаксации переменных решения СЛАУ. Кубическая зависимость числа арифметических операций от размера матрицы СЛАУ приводит при Метод релаксации переменных решения СЛАУ к нереально большому времени решения даже на самых современных ЭВМ. Кроме того, время решения несоразмерно возрастает при использовании прямых методов в случае Метод релаксации переменных решения СЛАУ по причине недостаточности объема оперативной памяти для хранения данных задачи.

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

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

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

1. МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ


Рассмотрим систему линейных алгебраических уравнений


Метод релаксации переменных решения СЛАУ,

(1.1)

где

А - матрица размерности Метод релаксации переменных решения СЛАУ,

x=(x1,x2,...,xn)T- вектор решения,

f=(f1,f2,...,fn)T - вектор правых частей.

Численные методы решения данной системы принято разделять на два класса: прямые методы и итерационные.

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

К прямым методам относятся метод Крамера, метод Гаусса, LU- метод, метод прогонки и ряд других методов. Основным недостатком прямых методов является то, что для нахождения решения необходимо выполнить большое число операций.

Суть итерационных методов состоит в том, что решение системы (1.1) находится как предел последовательных приближений x(n) при n®Ґ, где n - номер итерации. Применение итерационных методов требует задания начального значения неизвестных х(0) и точности вычислений e>0. Вычисления проводятся до тех пор, пока не будет выполнена оценка


Метод релаксации переменных решения СЛАУ.

(1.2)

Основное достоинство итерационных методов состоит в том, что точность искомого решения задается.

Число итераций n=n(e), которое необходимо выполнить для получения заданной точности e, является основной оценкой качества метода. По этому числу проводится сравнение различных методов.

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

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

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

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

Заметим, что существуют системы, для которых итерационный процесс сходится, а вектор невязки, получающийся при подстановке найденного решения в исходную систему


Метод релаксации переменных решения СЛАУ,

(1.4)

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

Продемонстрируем применение одношагового итерационного метода Якоби на решении системы трех уравнений. Пусть система (1.1) имеет видМетод релаксации переменных решения СЛАУ

(1.5)



начальное приближение Метод релаксации переменных решения СЛАУ (верхний индекс указывает номер итерации), требуемая точность решения - e. Первая итерация находится из выражения


Метод релаксации переменных решения СЛАУ


(1.6)


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


Метод релаксации переменных решения СЛАУ


(1.7)


Если точность не достигнута, то выполняется следующая итерация. В системе (1.5) Метод релаксации переменных решения СЛАУ заменяем на Метод релаксации переменных решения СЛАУ и находим значения Метод релаксации переменных решения СЛАУ. После этого вновь проверяем, достигнута точность решения или нет.

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

Запишем выражение i+1- итерации через i:


Метод релаксации переменных решения СЛАУ


(1.8)


Если точность решения достигнута, то счет прекращается.

Для систем m-го порядка имеем


Метод релаксации переменных решения СЛАУ


(1.9)


Запишем метод простых итераций в матричной форме. Представим матрицу А в виде суммы трех матриц


А=А1+D+A2, (1.10)

где D = diag[a11, a22, ...,amm] - диагональная матрица,

А1= Метод релаксации переменных решения СЛАУ- нижняя треугольная матрица,

А2= Метод релаксации переменных решения СЛАУ- верхняя треугольная матрица.

Представим систему (1.1) в матричной форме


Метод релаксации переменных решения СЛАУ

(1.11)

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


Метод релаксации переменных решения СЛАУ,

(1.12)

Или


Метод релаксации переменных решения СЛАУ,

Метод релаксации переменных решения СЛАУ.


(1.13)


Существуют итерационные методы, обладающие лучшей скоростью сходимости, чем методы Якоби. В этих методах при вычислении i+1 итерации Метод релаксации переменных решения СЛАУ компоненты вектора решения используются, найденные на i+1 итерации компоненты решения с номерами Метод релаксации переменных решения СЛАУ, l=1,2,...,j-1. Наиболее распространенным методом подобного типа является метод Зейделя. Продемонстрируем его применение на системе (1.3). Вновь, задавая начальное приближение, для первой итерации запишем


Метод релаксации переменных решения СЛАУ


(1.14)


После проверки условия сходимости совершаем вторую итерацию и т.д. Для i+1 итерации запишем


Метод релаксации переменных решения СЛАУ


(15)

Общая формула имеет вид


Метод релаксации переменных решения СЛАУ.

(1.16)

Запишем метод Зейделя в матричной форме


Метод релаксации переменных решения СЛАУ,

(1.17)

или в форме близкой к каноническому виду


Метод релаксации переменных решения СЛАУ,

(1.18)

Метод релаксации переменных решения СЛАУ.

(1.19)

Для одношаговых итерационных методов, существует каноническая форма записи


Метод релаксации переменных решения СЛАУ.

(1.20)

Здесь Метод релаксации переменных решения СЛАУ- матрица, задающая тот или иной итерационный метод, Метод релаксации переменных решения СЛАУ- итерационный параметр. В случае метода Якоби Метод релаксации переменных решения СЛАУ- это матрица D, а Метод релаксации переменных решения СЛАУ=1, в случае метода Зейделя Метод релаксации переменных решения СЛАУ=D+А1, а итерационный параметр также равен единице Метод релаксации переменных решения СЛАУ=1.

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

Одним из наиболее распространенных одношаговых итерационных методов является метод верхних релаксаций*, который имеет следующий вид


Метод релаксации переменных решения СЛАУ,

(1.21)

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

Для получения расчетных формул (1.21) перепишем в виде


Метод релаксации переменных решения СЛАУ,

(1.22)

или в покомпонентной записи получим


Метод релаксации переменных решения СЛАУ.

(1.23)

Приведем несколько строк покомпонентной записи


Метод релаксации переменных решения СЛАУ,

(1.24)

Метод релаксации переменных решения СЛАУ,

(1.25)

Метод релаксации переменных решения СЛАУ

(1.26)

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

Рассмотрим итерационные методы с постоянным итерационным параметром, записанные в виде


Метод релаксации переменных решения СЛАУ.

(1.27)

Теорема 1.

Пусть А - симметричная положительно определенная матрица, t>0 и пусть выполнено неравенство В-0,5tА>0. Тогда итерационный метод (1.27) сходится.

Следствие 1.

Пусть А - симметричная положительно определенная матрица с диагональным преобладанием, т.е.


Метод релаксации переменных решения СЛАУ

(1.28)

Тогда метод Якоби сходится.

Следствие 2.

Пусть А - симметричная положительно определенная матрица. Тогда метод верхних релаксаций сходится при условии 0<w<2. В частности, метод Зейделя сходится (w=1).

Теорема 2.

Итерационный метод (1.27) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы Метод релаксации переменных решения СЛАУ по модулю меньше единицы.

Теорема 3.

Пусть А и В - симметричные положительно определенные матрицы, для которых справедливы неравенства Метод релаксации переменных решения СЛАУ, где g1,g2 - положительные постоянные, g1>g2. При Метод релаксации переменных решения СЛАУ итерационный метод (1.27) сходится и для погрешности справедливы оценки


Метод релаксации переменных решения СЛАУ, i=0,1,...,

(1.29)

Где


Метод релаксации переменных решения СЛАУ

(1.30)

Метод релаксации переменных решения СЛАУ,

(1.31)

Метод релаксации переменных решения СЛАУ,

(1.32)

Метод релаксации переменных решения СЛАУ.

(1.33)

Следствие 1.

Если АТ=А>0, то для метода простой итерации


Метод релаксации переменных решения СЛАУ

(1.34)

при


Метод релаксации переменных решения СЛАУ

(1.35)

справедлива оценка

Метод релаксации переменных решения СЛАУ,

(1.36)

где


Метод релаксации переменных решения СЛАУ

(1.37)

Метод релаксации переменных решения СЛАУ

(1.38)

Следствие 2.

Для симметричной матрицы А и


Метод релаксации переменных решения СЛАУ

(1.39)

справедливо равенство


Метод релаксации переменных решения СЛАУ,

(1.40)

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

Оценим число итераций n0(e), которое требуется для достижения заданной точности e в случае малых x, т.е. для получения оценки


Метод релаксации переменных решения СЛАУ.

(1.41)

Из условия Метод релаксации переменных решения СЛАУ получаем, что

Метод релаксации переменных решения СЛАУ,

(1.42)

и при малых x имеем


Метод релаксации переменных решения СЛАУ.

(1.43)

Заметим, что в качестве критерия сходимости итерационного метода может использоваться невязка, которая получается при подстановке найденного решения в систему (1.1).


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

линейный уравнение итерационный релаксация

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

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

Еще одно достоинство итерационного метода верхних релаксаций состоит в том, что при его реализации на ЭВМ алгоритм вычислений имеет простой вид и позволяет использовать всего один массив для неизвестного вектора.

Основная вычислительная формула имеет вид


Метод релаксации переменных решения СЛАУ

(1.44)

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


Метод релаксации переменных решения СЛАУ.

(1.45)

Действительно, при последовательном нахождении элемента Метод релаксации переменных решения СЛАУ( i+1 итерации) на каждом шаге будут использоваться найденные ранее значения, которые при k<j соответствуют i +1 итерации, а при k>j - i итерации.

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


1.2 Вычислительные погрешности метода верхних релаксаций


Один из основных вопросов применения итерационных методов связан с корректностью выбора точности метода e.

Анализируя вычислительные погрешности выражения (1.45), получим оценку наименьшего значения точности метода верхних релаксаций.

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

Запишем разность двух итерационных приближений решения и оценим её минимальное значение


Метод релаксации переменных решения СЛАУ

(1.46)

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


Метод релаксации переменных решения СЛАУ

(1.47)

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


Метод релаксации переменных решения СЛАУ,

(1.48)

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

1.3 Метод блочной релаксации


Исходная матрица Метод релаксации переменных решения СЛАУ разбивается на блоки (в рамках лабораторной работы будем рассматривать случай, когда Метод релаксации переменных решения СЛАУ

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: