Системы линейных уравнений в информатике (7 видео)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда решение системы 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. Если для погрешности итерационного метода выполняются оценки

Видео:Решение системы линейных алгебраических уравнений (СЛАУ) в Excel МАТРИЧНЫМ МЕТОДОМСкачать

Использование компьютерных технологий при решении систем линейных алгебраических уравнений

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

Тема : Использование компьютерных технологий при решении систем линейных алгебраических уравнений

научиться решать системы линейных алгебраических уравнений с помощью MS Excel ;

закрепить умения работать с мастером «Функций»;

выработать пошаговый алгоритм создания необходимых формул;

выработать пошаговый алгоритм решения систем разными способами;

научиться пользоваться справочными материалами, используя справку « Excel » и сеть Интернет ;

развивать познавательный интерес, творческую активность учащихся;

формирование ответственного отношения к учению на основе мотивации к обучению и познанию;

соблюдение правил работы на компьютере;

уважение к мыслям и настроениям другого человека, доброжелательное отношение к людям.

принимать и сохранять учебную задачу;

оценивать совместно с учителем результат своих действий.

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

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

использовать новые слова и термины в речи.

развивать дружеское и деловое общение учащихся в совместной работе;

формирование умения формулировать мысль.

Технологии: игровые технологии, личностно-ориентированные,

Формы организации процесса обучения: индивидуальная, фронтальная.

Методы обучения: репродуктивный, частично-поисковый, информационно-

Оборудование: ПК, программное обеспечение – MS Excel , Opera , тестирующая программа, мультимедийная доска, инструкции выполнения лабораторного задания, карточки проверочных заданий.

Целеполагание. Мотивация студентов

Постановка цели занятия.

Изучение нового материала:

Математические функции MS Excel$

Лабораторная работа за компьютером

Постановка домашнего задания.

Подведение итогов урока.

I. Организационный момент.

Проверка присутствующих, наличие тетрадей ручек.

II. Мотивация студентов.

В современном мире во все отрасли деятельности человека внедрились компьютерные технологии, которые помогают ускорить многие процессы решения поставленных целей. И не смотря на свою стабильность и точность, математики также требует к себе «компьютерного внимания». Для помощи решения многих математических задач существует множество математических программ и процессоров. Моей одной из любимых является программа Mathcad — система компьютерной алгебры из класса систем автоматизированного проектирования , ориентированная на подготовку интерактивных документов с вычислениями и визуальным сопровождением, отличается легкостью использования и применения для коллективной работы. Mathcad был задуман и первоначально написан Алленом Раздовом из Массачусетского технологического института (MIT), соучредителем компании Mathsoft , которая с 2006 года является частью корпорации PTC (Parametric Technology Corporation).

Mathcad имеет интуитивный и простой для использования интерфейс пользователя. Для ввода формул и данных можно использовать как клавиатуру, так и специальные панели инструментов.

Примеры из презентации.

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

Примеры из презентации.

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

Слайд презентации: тема и цели занятия.

Тема занятия: «Использование компьютерных технологий при решении систем линейных алгебраических уравнений».

I II. Актуализация знаний.

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

I V . Изучение нового материала.

Записать в тетрадь

Рассмотрите внимательно алгоритмы решения систем уравнений матричным методом и методом Крамера.

Подведение промежуточного итога:

Комментарии к выполнению лабораторного задания, оформление отчета:

Правильность заполнения формулами ячеек матриц (массивов);

Использование контекстного меню для оформления листа «Отчет».

Переход в компьютерный класс.

V I . Лабораторная работа за компьютером

для проведения лабораторного занятия №

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

Цель: Научиться применять полученные знания для визуальной демонстрации выполнения различных условий.

Рабочее место: Лаборатория информатики и вычислительной техники.

Продолжительность занятия: 45 мин.

Материальное техническое оснащение рабочего места: персональный компьютер; операционная система Windows, табличный процессор.

Правила охраны труда

1. Трогать экран с тыльной стороны дисплея, проводов питания и устройств заземления.

2. Нарушать порядок включения / выключения аппаратурных блоков, стараться самостоятельно устранить выявленную неисправность в работе аппаратуры.

3. Класть на аппаратуру посторонние предметы.

4. Работать на компьютере во влажной одежде и с влажными руками.

Сведения из теоретической части работы

Excel – это пакет прикладных программ, ориентированный на обработку данных, представленных в табличной форме. Именно поэтому его часто называют табличным процессором, или электронной таблицей.

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

Формула в Excel – это совокупность арифметических операций, адресов ячеек и функций. Введение формул начинается со знака «=».

Функция – это заранее определенная формула, выполняет вычисления по заданным величинам, которые называются аргументами. Функции позволяют выполнять простые и сложные вычисления.

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

Вычисление обратной матрицы

Помните, что после ввода формулы, следует выделить нужный диапазон ячеек, нажать клавишу F2, а затем — клавиши CTRL+SHIFT+ВВОД. Если формула не будет введена как формула массива, то отображаться будет единственное значение.

Последовательность выполнения заданий

В своей папке создать Книгу ЕТ под названием « Решение систем »

Первый лист книги переименовать на « Пример 1 ». Выполнить с помощью табличного процессора решение следующего примера.

№ 1.Найти решение системы матричным способом

Создадим матрицу A , вектор В и обратную матрицу А -1 .

Для нахождения корней системы или значений вектора X , применим функцию МУМНОЖ(матрица А -1 ; матрица В).

Сделать проверку АХ = В =МУМНОЖ( матрица А; вектор Х )

Второй лист книги переименовать на « Пример 2 ». Выполнить с помощью табличного процессора решение следующего примера.

№ 2 Найти решение системы методом Крамера

1. Создадим матрицы: главную A и дополнительные A ₁ , A ₂ , A _3.

2. Вычислим значения соответствующих детерминантов матриц с помощью функции МОПРЕД.

3. Найдем корни системы используя формулу

Создать в данной книге лист 3 с названием « Метод 1 », где самостоятельно продемонстрировать решение матричным способом следующую систему уравнений

Создать в данной книге лист 4 с названием « Метод 2 », где самостоятельно продемонстрировать решение методом Крамера систему уравнений пункта 3.

Результату решений пунктов 4 и 5 оформить на листе 6 « Отчет » по следующему образцу

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

С помощью глобальной сети Интернет дополнить свой Отчет учеными-математиками (фамилия, имя, даты жизни, страна), которые внесли свой вклад в развитие решений систем линейных алгебраических уравнений:

Критерии оценивания работы

В работе должны присутствовать:

Ссылки на ячейки и рабочие листы;

Соответствие названий всех элементов с инструкцией;

Форматирование всех листов;

Оформление листа «Отчет» по образцу.

Оценка «3» — выполнение 1и 2пункта работы;

Оценка «4» — выполнение пунктов 1-4;

Оценка «5» — выполнение всех пунктов инструкции.

Решить систему матричным способом и методом Крамера проверив правильность решения с помощью табличного процессора

Ответ: x =-1; y =0; z =1.

VII. Постановка домашнего задания.

Решить систему линейных алгебраических уравнений

VII I. Подведение итогов урока.

Выполнение компьютерного теста.

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

«На сегодняшнем уроке я понял, я узнал, я разобрался…»;

Видео:Метод Крамера за 3 минуты. Решение системы линейных уравнений - bezbotvyСкачать

Решение систем линейных уравнений с помощью ЭВМ

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ С ПОМОЩЬЮ ЭВМ

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

Система m линейных алгебраических уравнений с n неизвестными в линейной алгебре — это система уравнений вида:

Здесь m — количество уравнений, а n — количество неизвестных. x1, x2, …, xn — неизвестные, которые надо определить. a11, a12, …, amn – коэффициенты при неизвестных системы, b1, b2,… bm — свободные члены. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

Решение системы m линейных алгебраических уравнений с n неизвестными — это совокупность n чисел (c1; c2; …; cn ) таких, что подстановка каждого ci вместо xi в систему обращает все её уравнения в тождества.

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

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

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

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

Алгоритм этого метода таков.

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

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

— Все элементы первой строки делят на верхний элемент выбранного столбца.

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

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

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

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

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

— Чтобы получить обратную матрицу, нужно применить все операции в том же порядке к единичной матрице.

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

Для системы n линейных уравнений с n неизвестными (над произвольным полем)

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

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

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

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

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

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

В численных методах разработаны целый ряд итерационных методов: метод Якоби, метод Зейделя, метод минимальных невязок и другие.

В моей исследовательской работе эти методы описаны подробно и подкреплены практическими задачами. Здесь же мы только называем эти методы.

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

В настоящее время разработан целый ряд дополнительных программных обеспечений(ПО), используемых для реализации итерационных методов (в частности, Excel, MathCad, Derive, Maple, Mathlab, Mathematica). Эти дополнительные ПО доступны каждому, они значительно упрощают решение систем линейных уравнений различных видов и различных степеней сложности.

1. Л, Солодовников . М.”Просвещение”.1974г. – С.160

2. Кондрашов зачетных заданий. Часть1. Красноярск. РИО КГПУ. 2001г. – С.102

3. Кураш высшей алгебры. М.”Наука”. 1971г. – С.432

4. , , “Численные методы”. М.”Академия”. 2005г. – С.384

5. Ларин алгебра. Часть1. Красноярск. РИО КГПУ. 2005г. – С.115

6. Окунев алгебра. М.”Просвещение”. 1968г. – С.336

7. Степанова лекций по курсу ”Численные методы”. Красноярск. РИО КГПУ. 2010г. – С.161

8. Степанова по курсу “Численные методы”. Красноярск. РИО КГПУ. 2003г. – С.66