Содержание
Введение
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
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-1A= 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) перестановка двух строк или столбцов;
2) умножение всех элементов какой-либостроки на одно и то же число, отличное от нуля;
3) сложение элементов какой-либо строкис соответствующими элементами другой строки, умноженными на одно и то же число.
В качестве примерарассмотрим метод [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эквивалентно совокупности элементарных преобразований над уравнениями системы.
Заключение
Проблемаповышения качества вычислений, как несоответствие между желаемым идействительным, существует и будет существовать в дальнейшем. Ее решению будетсодействовать развитие информационных технологий, которое заключается как всовершенствовании методов организации информационных процессов, так и ихреализации с помощью конкретных инструментов – сред и языков программирования.
Списоклитературы
1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов[Текст] И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с.
2. Васильев, Ф.П.Численные методы решения экстремальных задач. [Текст] Ф.П. Васильев – М.: Наука, 2002. C. 415.
3. Симанков, В.С.Основы функционального программирования [Текст] В.С. Симанков, Т.Т. Зангиев,И.В. Зайцев. – Краснодар: КубГТУ, 2002. –160 с.
4. Калиткин, Н.Н.Численные методы. [Электронный ресурс] Н.Н. Калиткин. – М.: Питер, 2001. С.504.
5. Кнут, Д.Э.Искусство программирования. Основные алгоритмы [Текст] Д.Э. Кнут. – М.:Вильямс, 2007. Т.1.– 712с.