Численные методы решения систем линейных уравнений презентация

Численные методы линейной алгебры. Методы решений нелинейных уравнений и систем. Лекция 3: — презентация

Презентация была опубликована 7 лет назад пользователемРоза Ядугина

Похожие презентации

Презентация на тему: » Численные методы линейной алгебры. Методы решений нелинейных уравнений и систем. Лекция 3:» — Транскрипт:

1 Численные методы линейной алгебры. Методы решений нелинейных уравнений и систем. Лекция 3:

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

3 П.1 Метод простой итерации. Рассмотрим систему линейных алгебраических уравнений n – го порядка, записанную в виде: (3.1), где — квадратичная числовая матрица n – порядка. — n – мерный вектор, неизвестная величина, которую требуется найти. — n – мерный вектор (известный, заданный столбец свободных членов). Задав начальное приближение, итерационный процесс нахождения приближенного решения (3.1) сформулируем следующим образом: (3.2) Выясним, при каких условиях на матрицу, решение найденное по методу простой итерации будет сходиться к решению задачи (3.1).

4 Практическая схема решения СЛАУ методом простой итерации Рассмотрим для простоты систему, состоящую из трёх уравнений с тремя неизвестными: 1). Преобразуем эту систему к системе вида: (3.3) где (3.4)

5 Этого можно добиться: 1) переставляя столбцы исходной системы; 2) меняя строки; 3) делая линейную комбинацию из строк. 2) из первого уравнения (3.3) выразим ; из второго уравнения (3.3) выразим ; из третьего уравнения (3.3) выразим ; Получим: Правая часть этой системы имеет нормальную матрицу

6 Учитывая (3.4) и обозначив через – точное решение, а через – n – тую итерацию, будем иметь Найдя с помощью вышеуказанного равенства, а также, выясним при каком номере N будет выполняться неравенство: Метод нахождения на n – й итерации имеет вид: В процессе выполнения этого итерационного процесса, на каждом шаге находим разность. Когда выполнение итерационного процесса прекращаем, решение найдено с заданной точностью.

7 3) На практике часто используется итерационный процесс Гаусса – Зейделя, который имеет вид: (3.5) Выясним при каких условиях сходится метод Гаусса – Зейделя. Теорема 3.1: Для того, чтобы решение по методу Гаусса – Зейделя существовало и было единственно, и для того, чтобы итерационный процесс (3.5) сходился, достаточно выполнение условий (3.4).

8 Методы решений нелинейных уравнений и систем п.1 Задача отделения корней Пусть требуется решить уравнение с одной неизвестной:, где — заданная функция. Задача определения корней для уравнения (3.6) f(x)=0 состоит в определении отрезков, которые содержат один и только один корень этого уравнения. Теорема 3.2: Пусть ф., f(a)f(b)

10 П.2. Метод Ньютона (метод касательных ) Пусть, f(a) f(b)

11 п.3. Метод хорд (метод секущих) П о методу хорд (k+1)е приближение решения находится с помощью равенства:

12 П.4 Комбинированный метод При использовании методов Ньютона и секущих мы приближаемся к точному решению с одной стороны. Комбинированный способ состоит в попеременном применении метода Ньютона и секущих, тогда приближение идет с двух сторон. При комбинированном методе приближение начинают делать с метода касательных. Точность вычислений. Пусть требуется решать уравнение (3.6) с точностью ε. ε= При использовании комбинированного метода точность приближения определяется формулой В качестве корня выбирается:

13 п.5. Метод итераций Пусть требуется решить уравнение (3.7), которое может не иметь решения, иметь одно решение или иметь бесконечное множество решений. Сформулируем теорему, которая дает достаточное условие, при котором это уравнение имеет единственное решение и укажем итерационный процесс для нахождения приближенного решения этого уравнения. Определение 3.1: Будем говорить, что ф. f(x) на [a,b] удовлетворяет условию Липшица с постоянной α, если будет справедливо неравенство: (3.8) Теорема 3.3: ] ф. на удовлетворяет условию Липшица с постоянной, тогда уравнение имеет единственное решение, причем, где, при этом имеют место оценки:

14 Литература Е. А. Волков Численные методы, М. Наука, 1987 ( либо последующие издания ): & 4-12, 15, 19-22, 24,25,

Презентация «Решение систем линейных уравнений различными методами»

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

«Актуальность создания школьных служб примирения/медиации в образовательных организациях»

Свидетельство и скидка на обучение каждому участнику

Выберите документ из архива для просмотра:

Выбранный для просмотра документ Автор.docx

Тема урока: «Решение систем линейных уравнений»

Использованные источники и литература:

Колмогоров А. Н., Юшкевич А. П. (ред.) Математика XIX века. М.: Наука.

Гиндикин С. Г. Рассказы о физиках и математиках. — издание третье, расширенное. — М.: МЦНМО, 2001. — ISBN 5-900916-83-9

Березкина Э. И. Древнекитайская математика. М., 1987.

Рыбников К. А. История математики. М., 1994.

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

Аннотация: целью работы являлась оценка различных методов решения систем линейных алгебраических уравнений с точки зрения вычислительной сложности и возможности применения средств вычислительной техники для решения СЛАУ. В презентации рассмотрены различные математические методы решения систем линейных уравнений. Показаны алгоритмы и примеры решения. Рассказывается о способах решения СЛАУ средствами MS Excel с алгоритмами и примерами. Приводится текст программы на языке программирования Pascal ABC и результат ее работы решения системы уравнений методом Гаусса. Дается краткая историческая справка о жизни ученых, занимавшихся данной проблемой. Приводятся примеры использования систем линейных уравнений.

Автор: Юрченко Лариса Викторовна

Должность: учитель информатики

Категория: высшая квалификационная категория

Место работы: МБОУ Щёлковский лицей №7 Щелковского муниципального района Московской области

E-mail : Oktober 1935@ mail . ru

Выбранный для просмотра документ Презентация решение систем линейных уравнений.ppt

Описание презентации по отдельным слайдам:

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

исследовать различные математические методы решения систем уравнений с n неизвестными; научить учащихся технологиям нахождения корней систем линейных алгебраических уравнений средствами MS Excel; показать вычисление корней системы уравнений методом Гаусса, используя программу на языке программирования Pascal ABC; создать презентацию для использования на уроках информатики и математики в классах с углубленным изучением предметов.

К решению систем линейных алгебраических уравнений сводятся многочисленные практические задачи (по некоторым оценкам более 75% всех задач). Можно с полным основанием утверждать, что решение линейных систем является одной из самых распространенных и важных задач вычислительной математики. Конечно, существует много методов и современных пакетов прикладных программ для решения СЛАУ, но для того, чтобы их успешно использовать, необходимо разбираться в основах построения методов и алгоритмов, иметь представления о недостатках и преимуществах используемых методов. Математика – наука молодых. Иначе и не может быть. Занятия математикой – это такая гимнастика ума, для которой нужны вся гибкость и вся выносливость молодости. Н. Винер

Системой m линейных уравнений с n неизвестными называется система вида где aij и bi (i=1,…,m; b=1,…,n) – некоторые известные числа, а x1,…,xn – неизвестные.

Система может иметь единственное решение. Система может иметь бесконечное множество решений. Например, Система может не иметь решения. Например,

Прямые методы: метод Гаусса; метод Гаусса-Жордана; метод Крамера; матричный метод. Итерационные методы: метод простой итерации (метод Якоби); метод Гаусса-Зейделя; метод релаксации. Метод решения хорош, если с самого начала мы можем предвидеть — и далее подтвердить это, — что, следуя этому методу, мы достигнем цели. Г. Лейбниц

При решении систем линейных уравнений по методу Крамера выполняется следующий алгоритм: — систему записывают в матричном виде; — вычисляют главный определитель системы: — вычисляют дополнительные определители системы: — если главный определитель системы не равен нулю, то находят значения всех неизвестных по формулам:

Дата рождения: 31 июля 1704 года Место рождения: Женева, Швейцария Дата смерти: 4 января 1752 года Место смерти: Баньоль-сюр-Сез, Франция Научная сфера: математика, философия, небесная механика швейцарский математик, ученик и друг Иоганна Бернулли, один из создателей линейной алгебры Габриэль Крамер

Из-за высокой вычислительной сложности метода (требуется вычисление n + 1 определителя размерности n x n), он не применяется для машинного решения больших СЛАУ. Время, необходимое на вычисление одного определителя примерно такое же, как и время на решение одной системы уравнений при использовании метода Гаусса. Однако он иногда используется при ручном счёте и в теоретических выкладках. Трудность решения в какой-то мере входит в само понятие задачи: там, где нет трудности, нет и задачи. Д. Пойа

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

Дата рождения: 30 апреля 1777 года Место рождения: Брауншвейг Дата смерти: 23 февраля 1855 года Место смерти: Гёттинген Страна: Брауншвейг-Люнебург Научная сфера: математика, физика, астрономия Альма-матер: Гёттингенский университет Карл Фридрих Гаусс немецкий математик, астроном и физик

менее трудоёмкий по сравнению с другими методами; применим к любой системе линейных уравнений; позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение; позволяет найти максимальное число линейно независимых уравнений — ранг матрицы системы; в силу простоты и однотипности выполняемых операций пригоден для счета на электронно-вычислительных машинах. Применение: нахождение матрицы, обратной к данной; определение ранга матрицы; численное решение СЛАУ в вычислительной технике

Хотя описанный выше метод повсеместно называется методом Гаусса, он был известен и до него. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах», составленном между I в. до н. э. и II в. н. э. В ней собраны 246 задач, изложенных в традиционном восточном духе: формулируется задача, сообщается готовый ответ и указывается способ решения.

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

Дата рождения: 1 марта 1842 года Место рождения: Эльванген, Королевство Вюртемберг Дата смерти: 17 апреля 1899 года Место смерти: Ганновер, Провинция Ганновер, Королевство Пруссия Научная сфера: геодезия, математика Место работы: политехникум, Карлсруэ Известен как разработчик метода Гаусса -Жордана Вильгельм Йордан немецкий геодезист

Для матричных операций в Excel предусмотрены функции: МОПРЕД – вычисление определителя матрицы; МОБР – вычисление обратной матрицы; МУМНОЖ – произведение матриц; ТРАНСП – транспонирование матрицы. …нужны ли математические знания для того, чтобы в максимальной степени использовать возможности, предоставляемые современным компьютером? Рискну предположить, что без них не обойтись. Ваннах М.

Матричный метод Алгоритм: — систему линейных уравнений записывают в матричной форме: AX = B, где A — основная матрица системы; B — столбцы свободных членов; X — столбцы решений системы; матричное уравнение умножают слева на A–1 (матрицу, обратную к матрице A). Так как A− 1A = E, то X = A -1B. Правая часть этого уравнения даст столбец решений исходной системы. Условием применимости данного метода является невырожденность матрицы A. Условием этого является неравенство нулю определителя матрицы A. .

Поиск решения Широкий класс экономических задач составляют задачи оптимизации. MS Excel располагает мощным средством для решения оптимизационных задач. Это инструмент-надстройка, который называется Поиск решения (Solver). Задачу решения СЛАУ можно свести к оптимизационной задаче. Для этого одно из уравнений, например, первое взять в качестве целевой функции, а оставшиеся n-1 рассматривать в качестве ограничений.

Паскаль — высокоуровневый язык программирования, один из наиболее известных. Широко применяется в обучении программированию учащихся и студентов. Система Pascal ABC основана на языке Delphi Pascal и призвана осуществить постепенный переход от простейших программ к модульному, объектно-ориентированному, событийному и компонентному программированию.

Первое условие, которое надлежит выполнять в математике, — это быть точным, второе — быть ясным и, насколько можно, простым. Л. Карно

Пример №1 Из некоторого листового материала необходимо выкроить 360 заготовок типа А, 300 заготовок типа Б и 675 заготовок типа В. При этом можно применять три способа раскроя. Количество заготовок, получаемых из каждого листа при каждом способе раскроя, указано в таблице: Правильному применению методов можно научиться только применяя их на разнообразных примерах. Г. Цейтен Тип заготовкиСпособ раскроя заготовки123 А321 Б162 В415

Пример №2 Три судна доставили в порт 6000 т чугуна, 4000 т железной руды и 3000 т апатитов. Разгрузку можно производить как непосредственно в железнодорожные вагоны для последующей доставки потребителям, так и на портовые склады. В вагоны можно разгрузить 8000 т, а остаток груза придется направить на склады. Необходимо учесть, что поданные в порт вагоны не приспособлены для перевозки апатитов. Стоимость выгрузки 1 т в вагоны составляет соответственно 4,30, 5,25 и 2,20 денежных единиц. Записать в математической форме условия полной разгрузки судов, если затраты на нее должны составить 58850 ден. ед. Главная сила математики состоит в том, что вместе с решением одной конкретной задачи она создаёт общие приёмы и способы, применимые во многих ситуациях, которые даже не всегда можно предвидеть. М. Башмаков

1. Изучив различные математические методы решения СЛАУ можно сделать вывод, что наиболее трудоемким является метод Крамера как при нахождении корней «вручную», так и при использовании табличного процессора MS Excel, при большом количестве уравнений нецелесообразно применять метод для машинного решения. 2. Наиболее трудным для изучения и требующим значительных трудозатрат при вычислении корней СЛАУ оказывается для учащихся метод Гаусса-Жордана . 3. Табличные формулы Microsoft Excel – очень мощное вычислительное средство, позволяющее находить корни СЛАУ быстрее и проще, чем при вычислении «руками». 4. При решении систем уравнений с помощью программы на языке программирования Pascal ABC скорость вычислений значительно выше, чем при решении в табличном процессоре Microsoft Excel, реализация алгоритма не вызывает затруднений,.

Краткое описание документа:

Аннотация: целью работы являлась оценка различных методов решения систем линейных алгебраических уравнений с точки зрения вычислительной сложности и возможности применения средств вычислительной техники для решения СЛАУ. В презентации рассмотрены различные математические методы решения систем линейных уравнений. Показаны алгоритмы и примеры решения. Рассказывается о способах решения СЛАУ средствами MS Excel с алгоритмами и примерами. Приводится текст программы на языке программирования Pascal ABC и результат ее работы решения системы уравнений методом Гаусса. Дается краткая историческая справка о жизни ученых, занимавшихся данной проблемой. Приводятся примеры использования систем линейных уравнений.

Презентация: Численные методы решения систем линейных алгебраических уравнений

Введение

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

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

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

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

Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет ЭВМ.

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

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

Учитывая важность выше указанных проблем, тему своей работы мы определили так: «Численные методы решения систем линейных алгебраических уравнений ».

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

Предметом исследования, является выявление эффективности и сравнительная характеристика методов.

· изучить и проанализировать литературу по проблемам численных методов;

· изучить научную и учебную литературу по теме «Численные методы решения систем линейных алгебраических уравнений;

· определить основные этапы изучения темы «Численные методы решения систем линейных алгебраических уравнений»;

· продемонстрировать на примерах использование методов.

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

Во введении обоснована актуальность темы исследования, определены объект, предмет, проблема и задачи исследования.

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

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

В заключении подведены итоги и сделаны основные выводы.

Глава I. Теоретические основы исследования

§1 ЧИСЛЕННЫЕ МЕТОДЫ

Разрешимость системы линейных уравнений.

Когда мы говорим о главной матрице системы линейных уравнений, то всегда имеем в виду квадратную матрицу nхn, т. е. матрицу с одинаковым количеством строк и столбцов. Это важно.

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

Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение (однозначное) тогда и только тогда, когда ее главный определитель не равен нулю: Δ ≠ 0.

Рассмотрим случай, когда определитель системы равен нулю. Здесь возможны два варианта:

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

2. Δ = 0 и хотя бы один дополнительный определитель Δxi ≠ 0. Это имеет место только тогда, когда коэффициенты при всех неизвестных xi, пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений [7].

1.1 Матричный метод решения систем линейных алгебраических уравнений

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

Рассмотрим матрицу, составленную из коэффициентов при неизвестных:

Свободные члены и неизвестные можно записать в виде матрицы столбцов:

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

Равенство (1) называется матричным уравнением или системой уравнений в матричном виде.

Матрица А коэффициентов при неизвестных называется главной матрицей системы.

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

Любую линейную систему уравнений можно записать в матричном виде. Например, пусть дана система:

Эта система из двух уравнений с тремя неизвестными – x, y,. В высшей математике можно рассматривать системы из очень большого числа уравнений с большим количеством неизвестных и поэтому неизвестные принято обозначать только буквой х, но с индексами:

Запишем эту систему в матричном виде:

Здесь главная матрица системы:

Расширенная матрица будет иметь вид:

Microsoft Office Excel . Если же говорить о программе Excel, которая является одной из наиболее известных в обработке электронных таблиц, то без преувеличения можно утверждать, что ее возможности практически неисчерпаемы.Обработка текста, управление базами данных — программа настолько мощна, что во многих случаях превосходит специализированные программы — редакторы или программы баз данных. Такое многообразие функций может поначалу запутать, нежели заставить применять их на практике. Но по мере приобретения опыта начинаешь по достоинству ценить то, что границ возможностей Excel тяжело достичь.За всю историю табличных расчетов с применением персональных компьютеров требования пользователей к подобным программам существенно изменились. В начале основной акцент в такой программе, как, например, Visi Calc, ставился на счетные функции. Сегодня, положение другое. Наряду с инженерными и бухгалтерскими расчетами организация и графическое изображение данных приобретают все возрастающее значение. Кроме того, многообразие функций, предлагаемое такой расчетной и графической программой, не должно осложнять работу пользователя. Программы для Windows создают для этого идеальные предпосылки.В последнее время многие как раз перешли на использование Windows в качестве своей пользовательской среды. Как следствие, многие фирмы, создающие программное обеспечение, начали предлагать большое количество программ для Windows.

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

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

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

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

1.2 Метод Гаусса – прямой и обратный ход

Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:

Будем считать, что a11 ≠ 0 (если это не так, то достаточно переставить первую и некоторую другую строку расширенной матрицы местами). Проведем следующие элементарные преобразования:

т.е. Ci-(ai1 /a11 )*C1, i = 2, 3, . m.

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

В результате получим матрицу:

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

Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А – aij, где I = j.

Повторим наши элементарные преобразования, но уже для элемента α22.

т.е. Ci -(αi2 /α22 )*C2, i = 3, . m.

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

Такие преобразования продолжаются до тех пор, пока матрица не приведется к верхнее — треугольному виду. Т. е. под главной диагональю не окажутся все нули:

Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид:

Отсюда легко можно найти значение первого корня – xn = δm /γmn .

Подставив это значение в предыдущее m-1-е уравнение, легко получим значение xn-1 -ого корня.

Таким образом, поднимаясь до самого верха обратным ходом метода Гаусса, мы последовательно найдем все корни системы уравнений [5].

Рассмотрим систему уравнений:

Главный определитель данной системы:

Т. е. система определена и разрешима. Решим ее по методу Гаусса.

Проведем прямой ход метода Гаусса, выписав предварительно расширенную матрицу системы:

Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C2 -(a21 /a11 )*C1 = C2 -(2/1)*C1 = C2 -2*C1 :

Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C3 -(a31 /a11 )*C1 = C3 -(-1/1)*C1 = C3 +C1 :

Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы. Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C3 -(a32 /a22 )*C2 = C3 -(1/-2)*C2 = C3 +1/2C2 :

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

Эта матрица эквивалентна системе:

Обратным ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х3 :

Корень x3 = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2×2 -3×3 = 1):

Корень x2 = 2/5 найден. Подставим его и корень х3 в верхнее (первое) уравнение системы (x1 -x2 +x3 = 0):

Вывод: Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:

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

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

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

1.3 Итерация для линейных систем

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

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

Разрешим первое уравнение системы относительно х1 :

х1 = (-a12 /a11 )х2 -a13 /a11 х3 -a14 /a11 х4 -a15 /a11 .

Затем разрешим второе уравнение относительно х2 и т. д. Тогда систему можно переписать в виде:

гдеα = -aik /aii, i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.

Система является частным случаем записи вида:

При этом линейная функция L1 фактически не зависит от х1 .

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

Подставляя эти значения в правые части системы (*), получим первые приближения:

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

Условия сходимости итерационного процесса.

Установим условия, выполнение которых обеспечит сходимость получающихся приближений к истинному (точному) решению системы х1, х2, х3, х4 .

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

Это условие можно сформулировать и более точно [20]:

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

1.4 Итерация Якоби

Рассмотрим систему линейных уравнений:

Уравнения можно записать в виде:

Это позволяет предложить следующий итерационный процесс:

или (другой вид записи)

Покажем, что если начать с точки P0= (х1(0), х2(0), х3(0), х4(0) ) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х1 = 1, х2 = 2, х2 = 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:

Новая точка P1 = (х1(1), х2(1), х3(1), х4(1) ) = (1.75, 3.375, 3), ближе, чем P0.

Итерация, использующая (3), генерирует последовательность точек , которая сходится к решению (2, 4, 3):

Этот процесс называется итерацией Якоби и может использоваться для решения определенных типов линейных систем [19].

1.5 Итерация Гаусса-Зейделя

Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.

Отметим, что итеративный процесс Якоби производит три последовательности – <х1(k) >, <х2(k) >, <х3(k) >, <х4(k) >. Кажется разумным, что х1(k+1) может быть использовано вместо х2(k ). Аналогично х1(k+1) и х2(k+1) можно использовать в вычислении х3(k+1). Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (3*):

Такой итерационный процесс даст результаты:

Т. е. к точному решению мы пришли уже на 10-ом шаге итерации, а не на 19, как в итерации Якоби [19].

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

Эти формулы как раз и задают собственно итерационный процесс.

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

Это условие можно сформулировать и более точно:

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

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

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

§1 ЧИСЛЕННЫЕ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Существуют два типа ме­тодов — прямые и итерационные. Мы рассматриваем прежде всего метод исключения Гаусса для систем об­щего вида и варианты — метод прогонки и методы мат­ричной прогонки для систем специального вида (с трех-диагональной или блочно-трех диагональной матрицами). Это — прямые методы. Их эффективность зависит от по­рядка системы n структуры матрицы.

При изучении итерационных методов мы трактуем си­стему уравнений как операторное уравнение первого ро­да Au = f и излагаем общую теорию итерационных ме­тодов для операторных уравнений при минимальных предположениях относительно оператора А. Общая тео­рия позволяет доказать сходимость итераций для метода Зейделя и метода верхней релаксации при минимальных ограничениях на оператор А. Рассмотрены два класса методов: 1) для случая, когда известны границы γi > О и γ2 >= γ1 спектра оператора А в некотором энергетиче­ском пространстве HD ; 2) для случая, когда границы γ1 и γ2 неизвестны. Весьма эффективным является попере­менно-треугольный метод.

Основная задача линейной ал­гебры — решение системы уравнений

Будем предполагать, что матрица А невырождена, так что уравнение Аи = 0 имеет только триви­альное решение, и система (1) имеет единственноерешение

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

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

Выбор того или иного численного метода зависит от многих обстоятельств — от имеющихся программ, от вида матрицы А, от типа расчета и др. Поясним слова «тип расчета». Возможны разные постановки задачи:

1) найти решение одной конкретной задачи (1);

2) найти решение нескольких вариантов задачи (1) с одной и той же матрицей А и разными правыми частями. Может оказаться, что неоптимальный для одной задачи метод является весьма эффективным для мно­говариантного расчета.

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

При теоретических оценках каче­ства алгоритмов их сравнение проводится по числу q ( e ) арифметических действий, достаточных для нахождения решения задачи с заданной точностью е > 0 [15].

Метод Гаусса. Имеется несколько вычислительных вариантов метода Гаусса, основанного на идее последо­вательного исключения. Процесс решения системы ли­нейных алгебраических уравнений Ax = f (1) по методу Гаусса состоит из двух этапов.

Первый этап (прямой ход). Система (1) приво­дится к треугольному виду

где x =( x 1 , .. ., xN -) — неизвестный, φ= (φ1,…, φN ) —известный векторы, В* — верхняя треугольная матрица.

Второй этап (обратный ход). Неизвестные х N , xN -1, . x 1 определяются по формулам (2) .

Метод квадратного корня. Этот метод пригоден для систем

с эрмитовой (в действительном случае — симметричной) матрицей А. Матрица А разлагается в произведение

где S — верхняя треугольная, D — диагональная матрица. Решение уравнения Аu=fсводится к последователь­ному решению двух систем

Метод квадратного корня требует порядка N2 /3 арифметических действий, т. е. при больших N он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.

1. Метод итераций для решения системы линейных алгебраических уравнений.

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

Для ее решения выбирается некоторое начальное приближение у0 H и последовательно находятся приближенные решения (итерации) уравнения (1). Значение итерации yh +1 выражается через известные предыдущие итерации yk , yk -1 ,… Если при вычислении yh +1 используется толь­ко одна предыдущая итерация yh , то итерационный метод называют одношаговым (или двухслойным) методом; если же yk +1 выражается через две итерации yk и yk -1, то метод называется двухшаговым (или трехслойным). Мы будем рассматривать в основном одношаговые методы. Будем считать, что А: H -> H — линейный оператор в конеч­номерном пространстве H со скалярным произведе­нием (•, •).

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

(7), где А: Н -> Н — оператор исходного уравнения (1), В: Н -> Н — линейный оператор, имеющий обратный В-1, k — номер итерации, τ1 τ2, . τk+1, . — итерационные параметры, τk+1 > 0. Оператор В может, вообще говоря, зависеть от номера k — для Для простоты изложения мы пред­полагаем всюду, что В не зависит от k .

Если В = Е — единичный оператор, то метод(8) называют явным: yh +1 находится по явной формуле

В общем случае, при В≠ Е, метод (7) называют не­явным итерационным методом: для определения yh +1 надо решить уравнение:

Естественно требовать, чтобы объем вычислений для ре­шения.системы Byk+1 = Fk был меньше, чем объем вы­числений для прямого решения системы Au=f

Точность итерационного метода (7) характеризуется величиной погрешности zh = ук — и, т. е. разностью между решением уравнения (7) и точным решением и исход­ной системы линейных алгебраических уравнений. Под­становка yk = zk + u в (2) приводит к однородному урав­нению для погрешности:

§2 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

2.1 Общие сведения

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

2.2.1 Описание метода

Рассмотрим СЛАУ вида

Ax = B, где А — матрица. (1)

Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру

xk → x*, где х* — решение заданной системы.

В конечном варианте система будет имееть вид:

x1 =c11 x1 +c12 x2 +c13 x3 +…c1n xn +d1

x2 =c21 x1 +c22 x2 +c23 x3 +…c2n xn +d1

x3 =c31 x1 +c32 x2 +c33 x3 +…c1n xn +d3

xn =cn1 x1 +cn2 x2 +cn3 x3 +…cnn xn +dn

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

Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

Для преобразования системы можно выполнить следующие операции:

x1= a11-1 (c1 -a12 x2 — a13 x3 -… — a1n xn )

x2= a22-1 (c2 -a21 x2 — a23 x3 -… — a2n xn )

xn= ann-1 (cn -an1 x2 — an3 x3 -… — an-1n xn-1 )

В результате получим систему:

x1= 0+ c12 x2 + c13 x3 -…+ c1n-1 xn-1 + c1n xn +d1

x2= c21 x2 +0 +c23 x3 +…+ c2n-1 xn-1 + c2n xn +d2

xn= cn1 x1 + cn2 x2 +cn3 x3 +…+ cnn-1 xn-1 + 0+dn

В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:

сij =-aij /aii, di =ci /aii (i,j=1,2,3…n, i<>j)

Итерационный процесс продолжается до тех пор, пока значения х1(k), х2(k), х3(k) не станут близкими с заданной погрешностью к значениям х1(k-1), х2(k-1), х3(k-1).

2.2.2 Решение СЛАУ методом простых итераций

Решить СЛАУ методом простых итераций с точностью .

Для удобства преобразуем систему к виду:

Принимаем приближение на 0-ом шаге:

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

На 5-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

На 6-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить [14].

2.3 Метод Зейделя

2.3.1 Описание метода

В этом методе результаты, полученные на k-том шаге, используются на этом же шаге. На (k+1) — й итерации компоненты приближения вычисляются по формулам:

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

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

2.3.2 Решение СЛАУ методом Зейделя

Решить СЛАУ методом Зейделя с точностью .

Эту систему можно записать в виде:

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

Для удобства преобразуем систему к виду:

Принимаем приближение на 0-ом шаге:

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

Необходимая точность достигнута на 4-й итерации. Таким образом, итерационный процесс можно прекратить [9].

2.4 Сравнительный анализ

Можно заметить, что в методе Зейделя быстрее мы достигаемой нужной точности, в нашем случае в точность была достигнута на 4-й итерации, когда в методе простых итераций она была достигнута на 6-й итерации. Но в то же время в методе Зейделя ставится больше условий. Поэтому вначале нужно произвести иногда довольно трудоемкие преобразования. В таблице 4.1 приведены результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации: