Перечислите способы решения систем линейных уравнений информатика

Методы решения систем уравнений с использованием электронных таблиц MS Excel

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

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

Графический метод решения систем уравнений.

Графический метод наглядно показывает решение систем уравнений, но недостатком этого метода считается:

— много времени уходит на построение графиков функций;

— погрешность при построении;

— погрешность нахождения корней системы уравнений.

Многие из этих минусов можно избежать с помощью электронных таблиц MS Excel.

Решить графически системы уравнений с помощью MS Excel.

Преобразуем данные системы и внесем данные в MS Excel. (см. Приложение1.xls)

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

Ответ: (0;-4), (2;-6)

Ответ: (2;-6)

Ответ: нет решений

Построив графики уравнений, выясните, сколько решений имеет система уравнений:

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

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

Запишем метод Крамера для систем 2-го порядка.

решение записывается в виде: , где

, ,

, система имеет единственное решение — ,

система имеет бесконечное множество решений.

система не имеет решения.

Для упрощения вычислений можно использовать электронные таблицы MS Excel. В MS Excel есть формула позволяющая упростить процесс подсчета определителя – функция МОПРЕД(диапазон ячеек) (Функция МОПРЕД – возвращает определитель матрицы). Введя коэффициенты системы в ячейки и применив данную функцию можно найти значение определителя матрицы и вычислить корни системы по формуле Крамера.

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

, ,

A	B	C	D	E	F	G
1	4	3
2	1	-4		=МОПРЕД(А1:В2)
3
4	2	3
5	-9	-4	х	=МОПРЕД(А4:В5)	х=	=D5/D2
6
7	4	2
8	1	-9	у	=МОПРЕД(А7:В8)	у=	=D8/D2

A	B	C	D	E	F	G
1	4	3
2	1	-4		-19
3
4	2	3
5	-9	-4	х	19	х=	-1
6
7	4	2
8	1	-9	у	-38	у=	2

Выясните, имеет ли решения система и сколько: а)

, ,

Ответ: система имеет бесконечное множество решений.

б)

Ответ: система не имеет решение.

Усложним работу. Рассмотрим решение системы 3 линейных уравнений с 3 неизвестными.

Система трёх линейных уравнений с тремя неизвестными.

, , ,

,

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

Министерство образования и науки Республики Беларусь

Белорусский государственный университет

информатики и радиоэлектроники

Факультет информационных технологий и управления

Кафедра Вычислительных Методов и Программирования

к курсовой работе

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

ст.гр.020603 Навроцкий А.А.

1. Анализ существующих методов решения задачи.

2. Описание используемого метода.

3. Анализ результатов.

Список использованной литературы.

Приложение (распечатка программы, результатов).

Решение систем линейных алгебраических уравнений (СЛАУ) является одной из основных задач линейной алгебры. Эта задача имеет важное прикладное значение при решении научных и технических проблем. Кроме того, является вспомогательной при реализации многих алгоритмов вычислительной математики, математической физики, обработки результатов экспериментальных исследований.

Применяемые на практике численные методы решения СЛАУ делятся на две группы — прямые и итерационные.

В прямых (или точных) методах решение системы получают за конечное число арифметических действий. К ним относятся известное правило Крамера нахождения решения с помощью определителей, метод последовательного исключения неизвестных (метод Гаусса) и его модификации, метод прогонки и другие. Сопоставление различных прямых методов проводится обычно по числу арифметический действий, необходимых для получения решения. Прямые методы являются универсальными и применяются для решения систем до порядка 10 3 . Отметим, что вследствие погрешностей округления при решении задач на ЭВМ прямые методы на самом деле не приводят к точному решению системы.

Итерационные (или приближенные) методы являются бесконечными и находят решение системы как предел при k®¥ последовательных приближений x ( k ) , где k — номер итерации. Обычно задается точность e, и вычисления проводятся до тех пор, пока не будет выполнена оценка ºx ( k ) – x ( k -1) º 2 числовым равенствам

.

Разложение матрицы A на множители обычно получают посредством алгоритма, который называется компактной схемой метода Гаусса. Элементы l_im и U_mi могут быть вычислены по формулам

Тогда решение системы Ax=b сводится к последовательному решению двух систем — Ly=b и Ux=y.

Рассмотренный метод можно применять к решению серии систем с одной и той же матрицей.

Метод простых итераций (Якоби).

Для решения итерационным методом система линейных алгебраических уравнений Ax = b должна быть приведена к виду x = Gx+f , где G — некоторая матрица, f — преобразованный вектор свободных членов. Затем выбирается начальное приближение — произвольный вектор x (0) — и строится рекуррентная последовательность векторов x (1) , x (2) . x ( k ) . по формуле

.

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

или .

Чем меньше норма матрицы G, тем быстрее сходится итерационный процесс.

Преобразование системы можно осуществить, просто решая каждое i-е уравнение относительно x_i :

.

Метод Якоби использует следующий алгоритм построения приближений:

.

Если A — матрица с доминирующей диагональю, т.е. , то метод Якоби сходится при любом начальном приближении x (0 ) .

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

Канонической формой одношагового итерационного метода решения СЛАУ называется его запись в виде

,

где B_k+1 — матрица, задающая тот или иной итерационный метод, t_k+1 — итерационный параметр. Числовые параметры t_k вводят для ускорения сходимости. Способ выбора итерационных параметров определяется при исследовании сходимости метода, когда выясняется при каких значениях параметров метод сходится и когда сходимость будет наиболее быстрой (соответствующие параметры называются оптимальными).

Итерационный метод называют явным, если B_k+1 — единичная матрица. Неявные итерационные методы имеет смысл применять лишь в том случае, когда решение системы уравнений с матрицей B_k требует меньше машинной памяти или времени или алгоритмически проще, чем решение исходной системы.

Методом простой итерации называют явный метод с постоянм параметром

, или,

где r ( k ) = Ax ( k ) -b — вектор невязки. Метод сходится для симметричных положительно определенных матриц при .

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

.

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

При втором способе вычисляют нормы невязки до начала итераций и на каждой итерации. Итерации прекращают при выполнении неравенства

.

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

,

Привет студент

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

Приднестровский государственный университет им. Т.Г. Шевченко

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем

КУРСОВАЯ РАБОТА

«Информатика и программирование»

тема: «ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ»

студентка группы ИТ13ДР62ИС1

Арабаджи Федор Иванович

ЗАДАНИЕ

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

«ПРОГРАММИРОВАНИЕ»

Студента группы ________ — ___________________

утверждена протоколом кафедры _________ № _____ от «____» ____________ 20___ г.

Цель курсовой работы:

Задачи курсовой работы:

Результаты курсовой работы:

График обязательных консультаций:

Дата сдачи записки на регистрацию «_____» __________20__ г.

Дата защиты курсовой работы «_____» __________20__ г.

Задание принял к исполнению «_____» __________20__ г. ___________/________________/

Руководитель работы ______________________ /________________/

СОДЕРЖАНИЕ

2 ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ………………………………….

2.3 Метод обратной матрицы…………………………………………….

3 РУКОВОДСТВО ПРОГРАММИСТА………………………………………..

3.1 Введение и общие сведения……………………………………………

3.2 Структура программного продукта………………………………….

3.4 Описание исходных текстов программного продукта…………….

3.5 Аппаратная и программная часть…………………………………….

3.6 Результаты тестирования и опытной эксплуатации………………….

4 РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ……………………………………….

4.3 Установка программного продукта……………………………….…..

4.4 Запуск и работа с программным продуктом…………………….……

4.5 Удаление программного продукта…………………………………….

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ…………………………….

Введение

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

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

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

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

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

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

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

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

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

1 постановка задачи

В данной курсовой работе необходимо создать программный продукт при помощи Windows Forms на языке C#, который представлял бы возможность:

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

Программа должна выполнять решение систем линейных уравнений методом Гаусса, методом Крамера или методом обратной матрицы.

Окно программы должно содержать:

• пункты меню: Файл, Правка, Примеры, Справка, О программе;
• поле выбора метода решения системы линейных уравнений;
• поле выбора количества уравнений в системе;
• поля для входных и выходных данных;
• кнопки операций.

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

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

2 описание предметной области

Решение систем линейных алгебраических уравнений – одна из фундаментальных задач математики. Система m линейных алгебраических уравнений с n неизвестными (или, линейная система, также употребляется аббревиатура СЛАУ) в линейной алгебре — это система уравнений вида (Рисунок 1)

Рисунок 1- Система уравнений

В системе уравнений (Рисунок 1) m является количеством уравнений, а n – количество неизвестных. x₁, x₂, … x_n – это неизвестные, которые надо определить. a₁₁, a₁₂, … a_mn – коэффициенты системы, а b₁, b₂, … b_m – свободные члены. Индексы коэффициентов (a_ij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

Существуют следующие способы решения систем линейных уравнений:

– метод обратной матрицы.

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

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

Далее приведено более подробное описание метода. Пусть исходная система будет вида (Рисунок 2):

Рисунок 2 — Исходная система уравнений

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

Рисунок 2.1 — Матрица A

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

Рисунок 2.2 — Матрица треугольного вида

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

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

Если хотя бы одно число β_i ≠ 0, где i > r, то рассматриваемая система несовместна, то есть у неё нет ни одного решения.

Пусть β_i ≠ 0 для любых i > r. Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом x (см. рисунок 2.3):

Рисунок 2.3- Несовместная система

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

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

Метода Крамера – способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы, причём для таких уравнений решение существует и единственно. Назван по имени Габриэля Крамера, предложившего этот метод в 1750 г.

Рисунок 2.4 — Система линейных уравнений

Для системы n линейных уравнений (рисунок 2.4) с n неизвестными с определителем матрицы системы ≠ 0, решение записывается по формуле показанном на рисунке 2.5:

Рисунок 2.5 — Нахождение решения

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

2.3 Метод обратной матрицы

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

Обратная матрица – такая матрица A −1 , при умножении на которую, исходная матрица A даёт в результате единичную матрицу E (формула 2.6).

Обратная матрица находится по формуле 2.7.

В формуле 2.7 det обозначает определитель.

Если необходимо решить систему линейных уравнений Ax = b, где b – ненулевой вектор, в который входят свободные члены, x – искомый вектор. Если обратная матрица A -1 существует, то x = A -1 b. В противном случае либо размерность пространства решений больше нуля, либо их нет вовсе.

3 ПРОграммная реализация решения задачи

3.1 Введение и общие сведения

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

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

• методом Гаусса;
• методом Крамера;
• методом обратной матрицы.

Данный программный продукт значительно упрощает получение корней систем линейных уравнений.

3.2 Структура программного продукта

В процессе разработки программного продукта были реализованы следующие формы:

• Formcs – форма приветсвия;
• MATrix.cs – форма, обеспечивающая решение систем линейных алгебраических уравнений методом Гаусса, методом Крамера или методом обратной матрицы по выбору пользователя;
• About.cs – форма, содержащая информацию о программном продукте.

На рисунке 3.1 изображена функциональная схема.