Рефетека.ру / Математика

Реферат: Численные методы линейной алгебры

Содержание


Введение

1. Метод Гаусса

2. Модификации метода Гаусса

3. Метод прогонки

4. Вычисление определителей

5. Вычисление обратных матриц

6. Итерационные методы

Заключение

Список литературы


Введение


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

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


Численные методы линейной алгебры (1)


В матричной форме система (1) представляется как


A X = B (2)


где

Численные методы линейной алгебры


Чтобы такая система уравнений имела единственное решение, входящие в нее n уравнений должны быть линейно независимыми. Необходимым и достаточным условием этого является неравенство нулю определителя данной системы, т.е. det A № 0. Алгоритмы решения систем уравнений такого типа делятся на прямые и итерационные.

1. Метод Гаусса


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

При использовании метода Гаусса задача решается в два этапа:

1) прямой ход;

2) обратный ход.

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

При обратном ходе производится вычисление значений неизвестных.

Прямой ход метода Гаусса. Для получения расчетных формул прямого хода преобразуем исходную систему (1), заменив элементы bi (Численные методы линейной алгебры) на ai,n+1. В результате система (1) будет иметь следующий вид


Численные методы линейной алгебры


Прямой ход выполняется за (n-1) шагов, причем на каждом шаге из уравнений с номерами k + 1, k + 2, …, n исключается неизвестное xk.

На первом шаге сначала первое уравнение делится на a11 № 0. Получим


Численные методы линейной алгебры (3)

где Численные методы линейной алгебры


Затем из каждого оставшегося уравнения вида

Численные методы линейной алгебры (Численные методы линейной алгебры)


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


Численные методы линейной алгебры (4)

где

Численные методы линейной алгебры


На втором шаге указанные выше действия повторяются над (n - 1) уравнениями системы (4), всеми кроме первого, с целью исключения переменной x2, где


Численные методы линейной алгебры


В итоге получим


Численные методы линейной алгебры

где

Численные методы линейной алгебры

Повторяя шаги прямого хода (n - 1) раз, окончательно получим систему уравнений треугольного вида


Численные методы линейной алгебры (5)

где

Численные методы линейной алгебры


При программной реализации прямого хода используется расширенная матрица коэффициентов Aў


Численные методы линейной алгебры,


для которой элементы имеют следующий смысл


1) Численные методы линейной алгебры - начальные значения;

2) Численные методы линейной алгебры - промежуточные значения;

3) Численные методы линейной алгебры - конечные значения.


Для определения элементов Численные методы линейной алгебры матрицы Aў на некотором k-ом шаге

(Численные методы линейной алгебры)

используются следующие расчетные формулы


Численные методы линейной алгебры


Обратный ход метода Гаусса. После приведения исходной системы уравнений (1) к треугольному виду (5) вычисляются значения корней по следующим формулам


Численные методы линейной алгебры


Таким образом, расчетные формулы обратного хода имеют вид


Численные методы линейной алгебры


Вычислительная сложность метода Гаусса оценивается как O(n3), причем для реализации прямого хода требуется около Численные методы линейной алгебры арифметических операций, а для обратного – около n2 операций.


2. Модификации метода Гаусса


Метод Гаусса с выбором главного элемента. Основным ограничением метода Гаусса является предположение о том, что все элементы Численные методы линейной алгебры, на которые производится деление на каждом шаге прямого хода, не равны нулю. Эти элементы называются главными элементами и располагаются на главной диагонали матрицы A.

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

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

Идея этого метода состоит в следующем. На некотором k-м шаге прямого хода из уравнений исключается не следующая по номеру переменная xk, а такая переменная, коэффициент при которой является наибольшим по абсолютной величине. Этим гарантируется отсутствие деления на нуль и сохранение устойчивости метода.

Если на k-м шаге в качестве главного элемента выбирается Численные методы линейной алгебрыЧисленные методы линейной алгебры, то в матрице Aў должны быть переставлены местами строки c номерами k и p и столбцы с номерами k и q.

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

Существуют две более простые модификации метода Гаусса:

- с выбором главного элемента по столбцу;

- с выбором главного элемента по строке.

В первом случае в качестве главного элемента выбирается наибольший по абсолютной величине элемент k-й строки (среди элементов Численные методы линейной алгебры, i = Численные методы линейной алгебры). Во втором - наибольший по абсолютной величине элемент k-го столбца (среди элементов Численные методы линейной алгебры, i = Численные методы линейной алгебры). Наибольшее распространение получила первый подход, поскольку здесь не изменяется нумерация переменных.

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

LU-разложение. В современном математическом обеспечении ЭВМ метод Гаусса реализуется с использованием LU-разложения, под которым понимают представление матрицы коэффициентов A в виде произведения A = LU двух матриц L и U, где L – нижняя треугольная матрица, U - верхняя треугольная матрица


Численные методы линейной алгебры


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


L Y = B; (6)

U X = Y (7)

линейный алгебраический уравнение численный

где Y = Численные методы линейной алгебры - вектор вспомогательных переменных.


Такой подход позволяет многократно решать системы линейных уравнений с разными правыми частями B. При этом наиболее трудоемкая часть (LU-разложение матрицы A) выполняется только один раз. Эта процедура соответствует прямому ходу метода Гаусса и имеет оценку трудоемкости O(n3). Дальнейшее решение систем уравнений (6) и (7) может выполняться многократно (для различных B), причем решение каждой из них соответствует обратному ходу метода Гаусса и имеет оценку вычислительной сложности O(n2).

Для получения LU-разложения можно воспользоваться следующим алгоритмом.

1. Для исходной системы (1) выполнить прямой ход метода Гаусса и получить систему уравнений треугольного вида (5).

2. Определить элементы матрицы U по правилу


uij = Cij (i = Численные методы линейной алгебры; j = Численные методы линейной алгебры)


3. Вычислить элементы матрицы L по правилам


Численные методы линейной алгебры


Расчетные формулы для решения системы (6) имеют следующий вид:


y1 = b1 / l11;

Численные методы линейной алгебры


Расчетные формулы для решения системы (7)


xn = yn;

Численные методы линейной алгебры (i = n - 1, n - 2, …, 1).


3. Метод прогонки


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


Численные методы линейной алгебры Численные методы линейной алгебры (8)


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

Преобразуем первое уравнение системы (8) к виду x1 = a1x2 + b1, где

a1 = -с1 / b1 и b1 = -d1 / b1. Подставим полученное для x1 выражение во второе уравнение системы (8)


a2(a1x2 + b1) + b2x2 + c2x3 = d2.


Представим это уравнение в виде x2 = a2x3 + b2, где a2 = -с2 / (b2 + a2a1) и b2 = (d2 - a2b1) / (b2 + a2a1). Полученное для x2 выражение подставим в третье уравнение системы (8) и т.д.

На i-м шаге (1 < i < n) процесса i-е уравнение системы принимает вид


xi = aixi+1 + bi, (9)

где ai = -сi / (bi + aiai-1) и bi = (di - aibi-1) / (bi + aiai-1).


На последнем n-м шаге подстановка в последнее уравнение системы (8) выражения xn-1 = an-1xn + bn-1 дает уравнение an(an-1xn + bn-1) + bnxn = dn, из которого можно определить значение xn = bn = (dn – anbn-1) / (bn + anan-1).

Значения остальных неизвестных xi (i = n-1, n-2, ..., 1) легко вычисляются по формуле (9).

Таким образом, алгоритм прогонки, подобно методу Гаусса, включает два этапа – прямой ход (прямая прогонка) и обратный ход (обратная прогонка).

Прямой ход метода прогонки состоит в вычислении прогоночных коэффициентов


ai (i = Численные методы линейной алгебры) и bi (i = Численные методы линейной алгебры).


При i = 1 эти коэффициенты вычисляются по формулам:


a1 = -с1 / g1; b1 = -d1 / g1; g1 = b1.


Для i = Численные методы линейной алгебры используются следующие рекуррентные формулы:


ai = -сi / gi; bi = (di - aibi-1) / gi; gi = bi + aiai-1.


Прямая прогонка завершается при i = n:

bn = (dn – anbn-1) / gn; gn = bn + anan-1.


Обратный ход метода прогонки позволяет вычислить значения неизвестных. Сначала полагают xn = bn. Затем в обратном порядке по формуле (9) определяют значения неизвестных xn-1, xn-2, ..., x1.

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

Теорема [2]. Пусть коэффициенты системы (8) удовлетворяют следующим неравенствам


пbkпіпakп+пckп; пbkп>пakп; k = Численные методы линейной алгебры, где a1 = 0; bn = 0. Тогда gi № 0 и пaiпЈ

1 для всех i = Численные методы линейной алгебры


Заметим, что при всех gi № 0 вычисления по формулам прямой прогонки могут быть доведены до конца (ни один из знаменателей не обратится в нуль). Одновременно все коэффициенты ai, такие, что пaiпЈ 1, обеспечивают устойчивость по входным данным этапа обратной прогонки по формуле (9).


4. Вычисление определителей


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

1) перестановка двух строк или столбцов определителя не изменяет его абсолютной величины, но меняет знак на противоположный;

2) умножение всех элементов одной строки или одного столбца на любое число равносильно умножению определителя на это число;

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

Пусть задан определитель


Численные методы линейной алгебры


Выберем главный элемент a11 № 0. Если a11 = 0, то выполним перестановку двух строк или столбцов этого определителя, чтобы получить a11 № 0.

Вынесем главный элемент a11 из первой строки за знак определителя


Численные методы линейной алгебры


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


Численные методы линейной алгебры

Разложим полученный определитель по элементам первого столбца, что даст понижение его порядка определителя на единицу


Численные методы линейной алгебры


Повторим указанную процедуру (n - 1) раз и окончательно получим


Численные методы линейной алгебры


Если при вычислении определителя производилась перестановка строк или столбцов (для выбора главного элемента), то


Численные методы линейной алгебры


где s – количество выполненных перестановок.

Таким образом, вычисление определителя detA некоторой матрицы A сводится к выполнению прямого хода метода Гаусса. Абсолютная величина этого определителя равна произведению главных элементов Численные методы линейной алгебры, k = Численные методы линейной алгебры, используемых на каждом шаге прямого хода. Знак определителя зависит от числа перестановок строк и столбцов, выполненных при выборе главных элементов.

Если такие перестановки не производились, то величина определителя также может быть вычислена как произведение диагональных элементов матрицы L, формируемой в процессе LU-разложения исходной матрицы А


Численные методы линейной алгебры


5. Вычисление обратных матриц


Обратную матрицу А-1 имеет любая квадратная матрица А, для которой detA № 0. Пусть дана матрица А = [aij]nґn. Для вычисления элементов обратной матрицы используется соотношение


A A-1 = A-1 A = E,


где E – единичная матрица.

Обозначим обратную матрицу A-1 = X = [xij]nґn. Тогда получим


A X = E.


Будем рассматривать столбцы матрицы X как векторы


Численные методы линейной алгебры Численные методы линейной алгебрыЧисленные методы линейной алгебры


Аналогично выделим столбцы единичной матрицы E


Численные методы линейной алгебры Численные методы линейной алгебры …; Численные методы линейной алгебры

Тогда система линейных уравнений вида


AЧисленные методы линейной алгебры = Численные методы линейной алгебры


позволяет определить элементы k-го столбца обратной матрицы X = A-1. Всего потребуется решить n таких систем с одинаковой матрицей A, но разными правыми частями Численные методы линейной алгебрыдля k = Численные методы линейной алгебры. Это можно сделать с использованием LU-разложения матрицы коэффициентов A, либо непосредственно с помощью метода Гаусса.


6. Итерационные методы


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


Численные методы линейной алгебры


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

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

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


Численные методы линейной алгебры.


Тогда переменную x1 можно выразить через первое уравнение, Численные методы линейной алгебры - через второе уравнение и т. д.


Численные методы линейной алгебры (10)

где Численные методы линейной алгебры и Численные методы линейной алгебры


Система (10) называется системой линейных уравнений, приведенной к нормальному виду. Матричная форма записи такой системы представляется как


Численные методы линейной алгебры (11)

где

Численные методы линейной алгебры

При решении системы (11) за нулевое приближение корней может быть принят столбец свободных членов, т.е. Численные методы линейной алгебры. Любое k-е приближение (Численные методы линейной алгебры вычисляется по формуле


Численные методы линейной алгебры


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


Численные методы линейной алгебры


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


Численные методы линейной алгебры (12)


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

Итерационный метод Зейделя. Метод Зейделя представляет собой модификацию метода последовательных приближений. При определении значения переменной Численные методы линейной алгебры на некоторой (k+1)-й итерации используются уже вычисленные (k+1)-е приближения неизвестных Численные методы линейной алгебры, Численные методы линейной алгебры, ..., Численные методы линейной алгебры, а также значения Численные методы линейной алгебры полученные на предыдущей k-й итерации.

Пусть дана линейная система уравнений (10). Выбранные начальные приближения корней Численные методы линейной алгебры подставляются в первое уравнение


Численные методы линейной алгебры


Для определения Численные методы линейной алгебры полученное значение Численные методы линейной алгебры сразу же подставляется во второе уравнение системы


Численные методы линейной алгебры


Аналогично определяются приближения корней Численные методы линейной алгебры. Значение Численные методы линейной алгебры вычисляется с использованием первых приближений всех переменных Численные методы линейной алгебры как


Численные методы линейной алгебры


В общем случае получение значений неизвестных Численные методы линейной алгебры по методу Зейделя на некоторой k-ой итерации производится по следующей формуле


Численные методы линейной алгебры


При использовании обозначений исходной системы уравнений (1) итерационная формула обычно записывается как


Численные методы линейной алгебры


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

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


Численные методы линейной алгебры


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

Таким образом, для сходимости указанных итерационных процессов достаточно, чтобы значения элементов aij матрицы a при i № j были небольшими по абсолютной величине. Можно показать, что для линейной системы вида (2) итерационные процессы последовательных приближений и Зейделя сходятся к точному решению X*, если для всех уравнений системы модули диагональных коэффициентов удовлетворяют условиям


Численные методы линейной алгебры

и по крайней мере для одного из уравнений выполняется соотношение


Численные методы линейной алгебры


Линейную систему (2) можно заменить такой эквивалентной системой нормального вида (11), которая удовлетворяет условиям сходимости итерационных процессов. Для этого используются следующие элементарные преобразования:

перестановка двух строк или столбцов;

умножение всех элементов какой-либо строки на одно и то же число, отличное от нуля;

сложение элементов какой-либо строки с соответствующими элементами другой строки, умноженными на одно и то же число.

В качестве примера рассмотрим метод [1] приведения линейной системы к виду, удобному для итераций. Система уравнений AX = B умножается на матрицу D = A-1 - D, где D = [dij] - матрица с малыми по модулю элементами. В результате получается эквивалентная система уравнений


(A-1 - D) A X = D B


или в нормальном виде


X = b + a X,


где a = D A и b = D B. Если значения кdij к достаточно малы, то очевидно, что полученная система вида (9) удовлетворяет условиям сходимости, поскольку умножение на матрицу D эквивалентно совокупности элементарных преобразований над уравнениями системы.

Заключение


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


Список литературы


Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с.

Васильев, Ф.П. Численные методы решения экстремальных задач. [Текст] Ф.П. Васильев – М.: Наука, 2002. C. 415.

Симанков, В.С. Основы функционального программирования [Текст] В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.

Калиткин, Н.Н. Численные методы. [Электронный ресурс] Н.Н. Калиткин. – М.: Питер, 2001. С. 504.

Кнут, Д.Э. Искусство программирования. Основные алгоритмы [Текст] Д.Э. Кнут. – М.: Вильямс, 2007. Т.1.– 712 с.

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

  1. • Численные методы решения систем линейных уравнений
  2. • Сравнительный анализ численных методов
  3. • Решение систем дифференциальных уравнений
  4. • Вычисление определителя матрицы прямым методом
  5. • Управление учебным процессом в колледже в период внедрения ...
  6. • Основные компоненты ЭВМ. Идеи и основы сети Интернет
  7. • Экзаменационные вопросы и билеты по линейной алгебре за ...
  8. • Алгебра октав
  9. • Численное решение системы линейных уравнений с ...
  10. • Абелевы универсальные алгебры
  11. • Точные методы численного решения систем линейных ...
  12. •  ... и задачи по курсу векторной и линейной алгебры
  13. • Поиск решений системы линейных уравнений методом ...
  14. • Конгруэнции Фраттини универсальных алгебр
  15. •  ... централизаторов конгруэнций универсальных алгебр
  16. • Основы линейной алгебры на примере балансовой модели
  17. • Дослідження універсальних абелевих алгебр
  18. • Доказательство Великой теоремы Ферма методами элементарной ...
  19. • Линейная алгебра и математическое программирование
Рефетека ру refoteka@gmail.com