Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Научные работы / Научная работа по теме "Численные методы решения систем линейных алгебраических уравнений"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Математика

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

библиотека
материалов

сОДЕРЖАНИЕ

введение………………………………………..……………………...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 Матричный метод решения систем линейных алгебраических уравнений

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

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

hello_html_m11b7e19.png

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

hello_html_509dbd3b.png

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

hello_html_57c75f2b.png

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

hello_html_m478e0d52.png

или

A·x = b. (1)

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

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

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

hello_html_m5f3850c7.png

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

hello_html_cbd59cd.png

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

hello_html_6bfb8ec1.png

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

hello_html_m300b522a.png

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

hello_html_3a9fb3c6.png

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

hello_html_m470a3e62.png

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

hello_html_m2dc5ccf3.jpg

Здесь x1, x2, …, xn - неизвестные, которые надо определить. а11, а12, …, аmn – коэффициенты системы — и b1, b2, …, bm — свободные члены — предполагаются известными. Индексы коэффициентов ij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

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

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

Решение системы (1.1) – совокупность n чисел с1, с2, …, сn, таких что подстановка каждого сi вместо xi в систему (1.1) обращает все ее уравнения в тождества.

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

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

Решения с1(1), с2(1), …, сn(1) и с1(2), с2(2), …, сn(2) совместной системы вида (1.1) называются различными, если нарушается хотя бы одно из равенств:

с1(1)1(2), с1(1)2(2), …, сn(1)n(2). (1.2)

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

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

hello_html_m578f686.jpg

или: Ах = В.

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


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

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


Microsoft Office Excel

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

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

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

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

MathCAD

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

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

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

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


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


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

hello_html_7de411bc.gif


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

(1.3)

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

hello_html_352cef4d.gif


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

(1.4)

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

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

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

hello_html_4cf1fdb5.gif


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

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

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

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

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

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

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

hello_html_m11b7e19.png

Прямой ход:

hello_html_m1fd2aabd.gif


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



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

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

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

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

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


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


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

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

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

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

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

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

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


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

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



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


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

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


hello_html_m4322d1cd.png (1.5)

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


hello_html_5c837ceb.png (1.6)

В этой форме формула Крамера справедлива без предположения, что отлично от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Также можно считать, что либо наборы b1, b2, …,bn и x1, x2, …,xn либо набор c1, c2, …,cn состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом.

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


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

Метод Гаусса

hello_html_m6395d5be.png

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

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


hello_html_m1705701a.png

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

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


hello_html_46222b3d.png

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

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

Метод Гаусса

hello_html_38d0b883.jpg

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

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

hello_html_m60755183.pnghello_html_m2fdfb2a5.png

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

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


hello_html_m6303e36f.pnghello_html_2b1b2b23.png

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












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

Метод Гаусса

hello_html_m428a5842.png

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













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

hello_html_m5aa85dd.png

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

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

hello_html_m6fad3c87.png

Рис.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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


27


Автор
Дата добавления 09.04.2016
Раздел Математика
Подраздел Научные работы
Просмотров247
Номер материала ДБ-019489
Получить свидетельство о публикации

Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Похожие материалы

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