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

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

Введение

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

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

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

(1)

Обозначим через вектор неизвестных и определим вектор-функцию Тогда система (1) записывается в виде уравнения:

(2)

Теперь вернёмся к всеми любимому Python и отметим его первенство среди языков программирования, которые хотят изучать [1].

Этот факт является дополнительным стимулом рассмотрения числительных методов именно на Python. Однако, среди любителей Python бытует мнение, что специальные библиотечные функции, такие как scipy.optimize.root, spsolve_trianular, newton_krylov, являются самым лучшим выбором для решения задач численными методами.

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

Так, в публикации [2], на основании проведенных вычислительных экспериментов, доказано, что библиотечная функция newton_krylov, предназначенная для решения больших систем нелинейных уравнений, имеет в два раза меньшее быстродействие, чем алгоритм TSLS+WD
(two-step least squares), реализованный средствами библиотеки NumPy.

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

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

Библиотечная функция scipy.optimize.root выбрана в качестве базы сравнения, потому что имеет обширную библиотеку методов, пригодных для сравнительного анализа.

scipy.optimize.root(fun, x0, args=(), method=’hybr’, jac=None, tol=None,callback=None, ptions=None)
fun — Векторная функция для поиска корня.
x0 –Начальные условия поиска корней

method:
hybr -используется модификация Пауэлл гибридный метод;
lm – решает системы нелинейных уравнений методом наименьших квадратов.
Как следует из документации [3] методы broyden1, broyden2, anderson, linearmixing, diagbroyden, excitingmixing, krylov являются точными методами Ньютона. Остальные параметры являются «не обязательными» и с ними можно ознакомится в документации.

Методы решения систем нелинейных уравнений

Приведенный далее материал действительно можно прочитать в литературе, например в [4], но я уважаю своего читателя и для его удобства приведу вывод метода по возможности в сокращенном виде. Те, кто не любит формулы, этот раздел пропускают.

В методе Ньютона новое приближение для решения системы уравнений (2) определяется из решения системы линейных уравнений:

(3)

Определим матрицу Якоби:

(4)

Запишем(3) в виде:

(5)

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

(6)

где — итерационные параметры, a — квадратная матрица n х n, имеющая обратную.

При использовании записи (6) метод Ньютона (5) соответствует выбору:

Система линейных уравнений (5) для нахождения нового приближения может решаться итерационно. В этом случае мы имеем двухступенчатый итерационный процесс с внешними и внутренними итерациями. Например, внешний итерационный процесс может осуществляться по методу Ньютона, а внутренние итерации — на основе итерационного метода Зейделя

При решении систем нелинейных уравнений можно использовать прямые аналоги стандартных итерационных методов, которые применяются для решения систем линейных уравнений. Нелинейный метод Зейделя применительно к решению (2) дает:

(7)

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

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

(8)

Выбор модельной функции

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

Функция f создаёт систему из n нелинейных уравнений, решение которой не зависит от числа уравнений и для каждой из n переменных равно единице.

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

Только один из методов, приведенных в документации [3] прошёл тестирование по результату решения модельной функции, это метод ‘krylov’.

Решение для n=100:

Вывод: С увеличением числа уравнений вдвое заметно появление ошибок в решении. При дальнейшем увеличении n решение становится не приемлемым, что возможно из-за автоматической адаптации к шагу, эта же причина резкого падения быстродействия. Но это только моё предположение.

Программа для тестирования на модельной функции c результатами решения системы алгебраических нелинейных уравнений с помощью программы написанной на Python 3 с учётом соотношений (1)-(8) для отыскания корней по модифицированному методу Ньютона

Решение для n=100:

Решение для n=200:

Solution:
[1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1.]
Newton iteration = 14
Newton method time 1.869 seconds

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

Получим:
Solution:
[ 0.96472166 0.87777036 0.48175823 -0.26190496 -0.63693762 0.49232062
-1.31649896 0.6865098 0.89609091 0.98509235]
Newton iteration = 16
Newton method time 0.046 seconds

Вывод: Программа работает и при изменении модельной функции.

Теперь вернёмся к начальной модельной функции и проверим более широкий диапазон для n, например в 2 и 500.
n=2
Solution:
[1. 1.]
Newton iteration = 6
Newton method time 0.048 seconds
n=500

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

Обращаем Ваше внимание, что в соответствии с Федеральным законом 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. Подведение итогов урока.

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

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

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

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

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

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

Система 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

источники:

http://infourok.ru/ispolzovanie_kompyuternyh_tehnologiy_pri_reshenii_sistem_lineynyh_algebraicheskih_uravneniy-469167.htm

http://pandia.ru/text/78/541/10665.php