Решение линейного уравнения в делфи

Об автоматическом дифференцировании (АД) на Хабре уже писалось здесь и здесь. В данной статье предлагается реализация АД для Delphi (протестировано в Embarcadero XE2, XE6) вместе с удобными классами методов Ньютона для решения нелинейных уравнений f(x) = 0 и систем F(X) = 0. Любые ссылки на готовые аналогичные библиотеки приветствуются, сам же я подобного не нашел, не считая отличного решателя СЛАУ с разреженной матрицей (см. под катом).

Давайте в самом начале отметим для себя, что выбор Delphi обусловлен legacy-кодом, тем не менее на C++ задачу можно решать следующим образом. Во-первых, для методов Ньютоновского (базовый метод Ньютона, метод Бройдена) типа имеются Numerical Recipes in C++. Ранее «Рецепты» были только на чистом C и приходилось делать свои классовые обертки. Во-вторых, можно взять одну из АД-библиотек из списка Autodiff.org. По моему опыту использования CPPAD быстрее FADBAD и Trilinos::Sacado примерно на 30%, самая же быстрая, судя по описанию, библиотека это новая ADEPT. В-третьих, для матрично-векторных операций можно взять проверенный временем uBlas , либо новые и быстрые конкуренты Armadillo и blaze-lib — это если для решения СЛАУ использовать отдельные библиотеки (например, SuiteSparce или Pardiso для прямых и ITL для итерационных методов). Привлекательным является также использование интегрированных библиотек линейной алгебры и решателей СЛАУ Eigen, MTL, PETSc (имеются также Ньютоновские решатели на C). Вся триада из заголовка полностью реализована, насколько мне известно, только в Trilinos.

Видео:Delphi линейный алгоритмСкачать

О применении численного дифференцирования

Производные можно вычислять аналитически и численно. К аналитическим методам относятся ручное дифференцирование, символьное (Maple, Wolfram и т.п.) и непосредственно автоматическое дифференцирование, выраженное в средствах выбранного языка программирования.

Современный тренд на использование АД оправдан одной простой причиной — с помощью этой техники устраняется избыточность кода и его дублирование. Другой аргумент состоит в том, что, например, при решении нелинейных дифференциальных уравнений (систем) сеточными методами способ вычисления F(X) сам по себе является нетривиальной задачей. В реальных задачах невязка F(X) представлена суперпозицией вызовов функций с разных слоев программы и ручное дифференцирование теряет свою наглядность. Следует также отметить, что при моделировании нестационарных процессов F(X) меняется на каждом шаге по времени, также может меняться и сам вектор неизвестных X. Использование АД позволяет нам сконцентрироваться непосредственно на формировании F(X), однако не снимает вопрос о верификации получаемой матрицы Якобиана dF(X)/dX. Дело в том, что при вычислении невязок мы можем забыть изменить тип промежуточной переменной со стандартного double на тип АД (а многие библиотеки имеют неявное приведение типа АД к double), тем самым некоторые производные будут вычислены некорректно. Проблема в этом случае состоит в том, что даже при наличии ошибок в формулах для производных метод Ньютона может сходиться, хоть и за возросшее число итераций. Это может быть незаметно при одних начальных данных и приводить к расходимости процесса при других.

Таким образом, какой бы аналитической способ дифференцирования df/dx не был выбран, его крайне желательно дополнить сравнением с численным дифференцированием (f(x + h) — f(x)) / h, иначе всегда будут оставаться сомнения в правильности кода. Естественно, численные производные никогда не совпадут с точностью с правильными аналитическими, тем не менее можно порекомендовать следующий прием юнит-тестирования. Можно выгрузить в текстовые файлы вектора X, F(X) и матрицу dF(X)/dX и выложить на SVN. Затем получить dF(X)/dX численно и сохранить файл поверх существующего, после чего визуально сравнивать файлы между собой. Здесь Вы всегда увидите насколько поменялись значения и сможете локализовать координаты элементов матрицы с большими отклонениями (не в долях) — в этом месте находится ошибка аналитического дифференцирования.

Видео:Delphi Квадратное уравнениеСкачать

Реализация АД

В Embarcadero Delphi до версии XE5 отсутствует возможность перегрузки арифметических операций для классов, но есть такая возможность для структур record (ссылка):

Обычно в АД на C++ размерность вектора производных является переменной величиной и инициализируется в конструкторе. В Delphi нельзя (есть попытки обойти) перегрузить оператор присваивания для структур и в связи с побитовым копированием вектор производных приходится делать фиксированной длины. Соответствующая константа TAutoDiff.n_all должна изначально задаваться вручную.

Пример 1

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

Видео:#9 Программирование в Delphi. Математические операцииСкачать

Реализация АД для разреженных матриц

С одной стороны фиксированное значение n_all это существенное ограничение, ведь размерность вектора может поступать извне. С другой стороны для некоторых задач его можно ослабить. Дело в том, что если говорить о численных методах решения уравнений механики сплошных сред, то возникающие в них матрицы имеют разреженную структуру — классический пример это «схема крест» для оператора Лапласа, когда в уравнении для узла с координатами (i, j) (ограничимся 2D) задействованы только 5 узлов: (i, j), (i-1, j), (i+1, j), (i, j-1), (i, j+1). Обобщая идею мы должны заложить следующее для данной конкретной задачи:

Пусть общее число узлов в решаемой задаче N. Тогда в матрице Якобиана N_all = N * n_junc_vars столбцов, из них ненулевых только n_all. Если завести теперь внутри структуры TAutoDiff целочисленный вектор n_juncs, каждый элемент которого определяет глобальный индекс узла от 0 до N-1, то функцию dx с локальным индексом из диапазона [0, n_all-1] можно дополнить функцией dx_global с уже глобальным индексом из диапазона [0, N_all-1]. Пример 2 иллюстрирует детали использования такого интерфейса, плюсы которого будут наиболее полно видны при реализации метода Ньютона ниже.

Пример 2

В следующей части планируется рассмотрение класса методов Ньютоновского типа, а также вопроса выбора разреженного решателя СЛАУ. Пока же предлагаю читателям:

• попробовать написать АД на C++11 с использованием семантики перемещений: 1) это должно работать очень быстро; 2) можно будет обойтись перегрузкой операторов без expression templates; 3) это будет впервые.
• идею для курсовой по реализации АД на Roslyn CTP: можно работать сразу с синтаксическим деревом, которое содержит всю информацию об арифметических выражениях в F(X).

Видео:ЛИНЕЙНЫЕ УРАВНЕНИЯ - Как решать линейные уравнения // Подготовка к ЕГЭ по МатематикеСкачать

Решение задач линейной алгебры средствами Delphi: Метод Гаусса для решения систем линейных алгебраических уравнений

Автор работы: Пользователь скрыл имя, 13 Июня 2013 в 19:21, курсовая работа

Краткое описание

Данная программа писалась на языке Delphi в бесплатной среде Lazarus. Lazarus — свободная среда разработки программного обеспечения для компилятора Free Pascal (часто используется сокращение FPC— свободно распространяемый компилятор языка программирования Pascal) на языке Object Pascal. Интегрированная среда разработки предоставляет возможность кроссплатформенной разработки приложений в Delphi-подобном окружении. На данный момент является единственным инструментом быстрой разработки приложений (RAD), позволяющим Delphi-программистам создавать приложения с графическим интерфейсом для Linux (и других не-Windows) систем.
Позволяет достаточно несложно переносить Delphi-программы с графическим интерфейсом в различные операционные системы: Linux, FreeBSD, Mac OS X, Microsoft Windows, Android. Начиная с Delphi XE2 в самом Delphi имеется возможность компиляции программ для Mac OS X и iOS.

Содержание

1. Введение 3
2. Содержательная часть 4
2.1. История 4
2.2. Описание метода 4
2.3. Условие совместности 5
3. Практическая часть. 6
3.1. Постановка задачи 6
3.2. Методы решения линейных уравнений 6
3.3. Руководство пользователя 7
3.4. Листинг 9
4. Заключение 17
5. Список литературы 18

Прикрепленные файлы: 1 файл

Видео:#6 Программирование в Delphi. МассивыСкачать

Kursovaya_po_obektno-orientirovannomu_programmi.docx

Захаров Д.С., ИСТ-21д

Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Себряковский филиал Волгоградского государственного архитектурно-строительного университета»
(ФГБОУ ВПО «СФ ВолгГАСУ»)

Кафедра Математических и естественно-научных дисциплин

Решение задач линейной алгебры средствами Delphi: Метод Гаусса для решения систем линейных алгебраических уравнений

по специальности 230400.62 «Информационные системы и технологии (бакалавр)»

Отрощенко Д.С., преподаватель

2. Содержательная часть 4

2.2. Описание метода 4

2.3. Условие совместности 5

3. Практическая часть. 6

3.1. Постановка задачи 6

3.2. Методы решения линейных уравнений 6

3.3. Руководство пользователя 7

4. Заключение 17

5. Список литературы 18

Видео:График линейной функции на Делфи | | Программирование на DelphiСкачать

Введение

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

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

Данная программа писалась на языке Delphi в бесплатной среде Lazarus. Lazarus — свободная среда разработки программного обеспечения для компилятора Free Pascal (часто используется сокращение FPC— свободно распространяемый компилятор языка программирования Pascal) на языке Object Pascal. Интегрированная среда разработки предоставляет возможность кроссплатформенной разработки приложений в Delphi-подобном окружении. На данный момент является единственным инструментом быстрой разработки приложений (RAD), позволяющим Delphi-программистам создавать приложения с графическим интерфейсом для Linux (и других не-Windows) систем.

Позволяет достаточно несложно переносить Delphi-программы с графическим интерфейсом в различные операционные системы: Linux, FreeBSD, Mac OS X, Microsoft Windows, Android. Начиная с Delphi XE2 в самом Delphi имеется возможность компиляции программ для Mac OS X и iOS.

Видео:Решение задачи в среде программирования Delphi.Скачать

Содержательная часть

Видео:Урок №1: Условия в Delphi - оператор "If Then" на примере программы "Решение квадратного уравнения"Скачать

История

Хотя в настоящее время данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах», составленном между I в. до н.э. и II в. н. э.

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

Описание метода

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

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

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

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

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

Если хотя бы одно число , где , то рассматриваемая система несовместна, т.е. у неё нет ни одного решения.

Пусть для любых .

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом ( , где — номер строки):

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

Видео:Delphi. Видеокурс. Урок 3Скачать

Условие совместности

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

Теорема Кронекера — Капелли.

Система совместна тогда и только тогда, когда ранг её основной матрицы равен рангу её расширенной матрицы.

Видео:Delphi 7 МатрицыСкачать

Практическая часть.

Видео:Как решать уравнения с модулем или Математический торт с кремом (часть 1) | МатематикаСкачать

Постановка задачи

Дана система из n линейных уравнений вида:

Видео:Delphi | Урок 4 - условные операторы (if else, case of)Скачать

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

Системы линейных уравнений вида (3) решаются точными и итерационными методами. Точные методы дают точное решение за конечное число операций, если все они выполнялись без погрешности. Число операций итерационных методов зависит от заданной погрешности вычислений. Метод Гаусса является точным методом решения системы линейных уравнений.

Метод Гаусса или метод последовательного исключения неизвестных основан на приведении матрицы коэффициентов А=(a_ij) к треугольному виду. При этом алгоритм решения системы линейных уравнений следующий:

1. С помощью двух циклов с управляющими переменными i=1,2. n и j=1,2,…,n организуется ввод коэффициентов a_ij и b_i образующих массивы A=(a_ij), B=(b_i).

2.Делается прямой ход исключения переменных путем преобразования коэффициентов по формулам:

В конце этих преобразований получается x_n=b_n/a_nn.

3.Организуется обратный ход (последовательное нахождение x_n-1, x_n-2 , …, x₂, x₁), проводя вычисления по формулам:

Особенностью метода Гаусса является то, что при прямом ходе производится выбор элемента строки отличного от нуля, если элемент a_ii, стоящий на главной диагонали матрицы А, равен 0.

Этот выбор осуществляется путем перестановки соответствующих строк матрицы А. Это исключает деление на 0, если матрица A=(a_ij) содержит нулевые элементы на главной диагонали.

Видео:Решение системы уравнений методом ГауссаСкачать

Руководство пользователя

Пользоваться данной программой довольно просто: начинать работу нужно с ввода коэффициентов при переменных x₁,x₂,x₃ (для удобства в программе были изменены на переменные X, Y, Z).

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

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

Затем при нажатии на кнопку «Ответ» программа выдаст результат:

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

Видео:Нахождение площади треугольника в DelphiСкачать

Листинг

Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, Grids,

Видео:Уравнения с модулемСкачать

2.3.2 Программная реализация решения системы линейных уравнений с помощью обратной матрицы стр.1

Delphi site: daily Delphi-news, documentation, articles, review, interview, computer humor.

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

Листинг 2.6. Фрагменты файла UMatrix pas, относящиеся к обращению матриц

unit UMatrix; interface

// ShowErrorMatrix — надо ли показывать окна с сообщениями // об ошибках

// Если ShowErrorMatrix = false, то ErrorMatrix показывает, // были ли ошибки, a MessageMatrix содержит

// последнее сообщение об ошибке

// Произведение матрицы на вектор

// Размерность матрицы должна быть М х N, а вектора N

// Прямое вычисление обратной матрицы

// Матрица А должна быть квадратной

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

// Матрица А должна быть квадратной

// Вектор VRi’ght той же размерности, что и А

function LSystem(const A: TMatrix; const VRight: TVector): TVector; implementation

uses Forms, // Для переменной Application

Windows, // Для обозначений флагов кнопок Application.MessageBox SysUtils, Math;// Для функции Abort

function ReversMatrix(const A: TMatrix): TMatrix; // Прямое вычисление обратной матрицы // с независимым расчетом определителя матрицы // Матрица А должна быть квадратной

Rtmp, Det: real; begin

ErrorMatrix := false; if (Length(A) = 0) then begin

#13’матрица не квадратная,1#13 +

‘ее размерность ‘ + IntToStr (N+l) + ‘ х ‘ +

Det := DetMatrix(A); if(Det = 0) then begin

SetLength(Matr, N+l, N+l); SetLength(Dop, N, N); for il:= 0 to N do

Rtmp := DetMatrix(Dop); if (Odd(il + jl) )

function ReversMatrix2(const A: TMatrix): TMatrix; // Прямое вычисление обратной матрицы

Rtmp, Det: real; begin

ErrorMatrix := false; if (Length(A) = 0) then begin