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

сОДЕРЖАНИЕ

 

введение………………………………………..……………………...4

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

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

1.2 Метод Гаусса……………………………………………………….....11

1.3. Метод Крамера……………………………………………………….15

2. РЕШЕНИЯ ПРАКТИЧЕСКИХ РАБОТ……………………………....17

2.1. Практика в excel.…………………………………………………...….17

2.2. Практика в pascal……………………………………………………..19

2.3. Практика в mathcad…………………………………………………...20

ЗАКЛЮЧЕНИЕ……………………………………………………………23

БИБЛИОГРАФИЧЕСКИЙ СПИСОК……………………………………24

Приложение А. Блок – схемы алгоритмов

Приложение Б. Код программы pascal

Введение

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

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

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

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

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

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

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

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

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

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

Задачи исследования:

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

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

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

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

Структура работы: научная работа состоит из введения, двух глав, заключения, библиографического списка.

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

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

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

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

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

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

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

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

или

A·x = b. (1)

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

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

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

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

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

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

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

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

Система т линейных уравнений с n неизвестными (или, линейная система) в линейной алгебре — это система уравнений вида

Здесь x₁, x₂, …, x_n - неизвестные, которые надо определить. а₁₁, а₁₂, …, а_mn – коэффициенты системы — и b₁, b₂, …, b_m — свободные члены — предполагаются известными. Индексы коэффициентов (а_ij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

          Система (1.1) называется однородной, если все ее свободные члены равны нулю (b₁=b₂=…=b_m=0), иначе неоднородной.

          Система (1.1) называется квадратной, если число m уравнений равно числу n неизвестных.

          Решение системы (1.1) – совокупность n чисел с₁, с₂, …, с_n, таких что подстановка каждого с_i вместо x_i в систему (1.1) обращает все ее уравнения в тождества.

Система (1.1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения.

Совместная система вида (1.1) может иметь одно или более решений.

Решения с₁⁽¹⁾, с₂⁽¹⁾, …, с_n⁽¹⁾ и с₁⁽²⁾, с₂⁽²⁾, …, с_n⁽²⁾ совместной системы вида (1.1) называются различными, если нарушается хотя бы одно из равенств:

с₁⁽¹⁾=с₁⁽²⁾, с₁⁽¹⁾=с₂⁽²⁾, …, с_n⁽¹⁾=с_n⁽²⁾.                     (1.2)

Совместная система вида (1.1) называется определённой, если она имеет единственное решение; если же у неё есть хотя бы два различных решения, то она называется неопределённой. Если уравнений больше, чем неизвестных, она называется переопределённой.

Система линейных уравнений может быть представлена в матричной форме как:

или: Ах = В.

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

Методы решения

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

Microsoft Office Excel

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

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

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

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

MathCAD

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

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

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

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

1.2 Метод Гаусса

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

Пусть исходная система выглядит следующим образом:

(1.3)

Матрица А называется основной матрицей системы, b – столбцом сводных членов.

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

(1.4)

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

Тогда переменные x_j1, …, x_jr называются главными переменными. Все остальные называются свободными.

Пусть b_i=0 для любых i>r.

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом x(a_ij, i=1 …, r, где i – номер строки).

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

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

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

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

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

Метод Гаусса требует порядка O(n³) действий. В простейшем виде случае алгоритм выглядит так:

Прямой ход:

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

Применение и модификация

Помимо аналитического решения метод Гаусса также применяется для:

·        нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: [A|E], после чего приводится к виду единичной матрицы методом Гаусса—Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица: [E|A^-1];

·        определения ранга матрицы (согласно следствию из теоремы Кронекера-Капелли ранг матрицы равен числу её главных переменных);

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

Достоинства метода

·                    Менее трудоемкий по сравнению с другими методами;

·                    Позволяет однозначно установить, совместна система или нет, и если совместна, найти ее решение;

·                    Позволяет найти максимальное число линейно независимых уравнений – ранг матрицы системы.

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

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

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

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

Метод Жордана – Гаусса используется для решения квадратных систем линейных алгебраических уравнений, нахождение обратной матрицы, нахождение координат вектора в заданном базисе, отыскания ранга матрицы. Метод является модификацией метода Гаусса. Назван в честь К.Ф. Гаусса и немецкого геодезиста и математика Вильгельма Йордана.

Метод Жордана – Гаусса отличается от метода Гаусса тем, что при выполнении вычислений прямого хода на k-м шаге делим k-e уравнение на a^(k-1)_kk (не равное 0) и выполняем дальнейшие вычисления с ведущим элементом, равным единице.

1.3. Метод Крамера

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

Для системы n линейных уравнений с n неизвестными с определителем матрицы системы △, отличным от нуля, решение записывается в виде:

 (1.5)

В другой форме правило Крамера формулируется так: для любых коэффициентов с₁, с₂, …, с_n справедливо равенство:

 (1.6)

В этой форме формула Крамера справедлива без предположения, что △ отлично от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Также можно считать, что либо наборы b₁, b₂, …,b_n и x₁, x₂, …,x_n либо набор c₁, c₂, …,c_n состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом.

ГЛАВА II. РЕШЕНИЯ ПРАКТИЧЕСКИХ РАБОТ

2.1. Практические в Excel

Метод Гаусса

Рис. 1 – Метод Гаусса excel

Метод Крамера

Рис. 2 – Метод Крамера excel

Матричный метод

Рис. 3 – Матричный метод excel

Практические в Pascal

Метод Гаусса

Рис.4 – Метод Гаусса pascal

Метод Крамера

Рис.5 – Метод Крамера pascal

Матричный метод

Рис.5 – Матричный метод pascal

Практические в Mathcad

Метод Гаусса

Рис.7 – Метод Гаусса mathcad

Метод Крамера

Рис.8 – Метод Крамера mathcad

Матричный метод

Рис.9 - Матричный метод mathcad
ЗАКЛЮЧЕНИЕ

     В результате проведенной нами работе было выявлено, что:

·        в MathCAD и Excel численные методы представляют собой те же самые общепринятые ручные расчёты, но выполняемые не человеком, а компьютером, что понижает возможность ошибки до нуля.

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

     В результаты все поставленные задачи были выполнены, цели достигнуты. Мы приобрели навыки в применении различных численных методов на практике. А также были исследованы различные методы.

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

1.         Алексеев Е., Чеснокова О. MATLAB 7. М., 2006, 464 с.

2.         Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы М.: Бином. Лаборатория знаний, 2003. - 632 с.

3.         Бахвалов Н.С. Численные методы. М.: Наука, 2006. 631 с.

4.         Березин И.С., Жидков Н.П. Методы вычислений, том 1 (2-е изд.). М.: Физматаит, 1962

5.         Ващенко Г.В. Вычислительная математика. Основы конечных методов решения систем линейных алгебраических уравнений. Красноярск: СибГТУ, 2005

6.         Ващенко Г.В. Вычислительная математика. Основы алгебраической и тригонометрической интерполяции. Красноярск: СибГТУ, 2008

7.         Ворожцов Е.В. Разностные методы решения задач механики сплошных сред (учебное пособие). Новосибирск: НГТУ, 1998

8.         Ворожцов Е.В. Сборник задач по теории разностных схем (учебное пособие). Новосибирск: НГТУ, 2000

9.         Демидович Б.П., Марон И.А. Основы вычислительной математики М.: Наука, 2006

10.    Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. Приближение функций, дифференциальные и интегральные уравнения. М.: Наука, 1967

11.    Дьяченко В.Ф. Основные понятия вычислительной математики. М.: Наука, 1972

12.    Калиткин Н.Н. Численные методы. М.: Наука, 2011, 592 стр.

13.    Кирьянов Д. Mathcad 12. СПб, 2004, 576с.

14.    Коткин Г., Черкасский В. Компьютерное моделирование физических процессов с использованием MathLab. Новосибирск, 2001.

15.    Крылов В.И. Приближенное вычисление интегралов (2-е изд.). М.: Наука, 1967

16.    Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы. Том II. М.: Наука, 1977.

17.    Кунцман Ж. Численные методы. М.: Наука, 1979.

18.    Лапчик М., Рагулина М., Хеннер Е. . Численные методы. М., 2004, 384 с.

19.    Марчук Г.И. Методы вычислительной математики. М.: Наука, 1977

20.    Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975

21.    Протасов И.Д. Лекции по вычислительной математике: учеб. пособ. - М.: Гелиос АРВ, 2009

22.    Поршнев С. В., Беленкова И. В.. Численные методы на базе Mathcad. СПб.: БХВ-Петербург, 2005. 464 с: ил.

23.    Потемкин В. Система MATLAB. Справочное пособие. М., 1997, 350 с.

24.    Тарасевич Ю. Численные методы на Mathcad'e. Астрахань, 2000, 70 с.

25.    Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969

26.    Хемминг Р.В. Численные методы (2-е изд.). М.: Наука, 1972