Глава 49. Линейные уравнения

Глава 49. Линейные уравнения

Содержание

Общие сведения

Идеи реализации

Линейные уравнения и METAPOST
Объектная модель капсулы
Упрощение линейных выражений
Исключение неизвестной
Класс Capsule

Разработка

Приготовления
Методы known и value
Метод simplify
Метод equation

Готовая программа

Общие сведения

Рассмотрим такую задачу из планиметрии: дан треугольник $A⁣ B⁣ C$ со сторонами $B⁣ C = a$ , $C⁣ A = b$ , $A⁣ B = c$ . Нужно найти отрезки, на которые стороны треугольника делятся точками касания со вписанной окружностью.

Здесь не помешала бы картинка.

Заметим, что $A⁣ Q = A⁣ R = p$ , $B⁣ R = B⁣ P = q$ , $C⁣ P = C⁣ Q = r$ (как касательные к окружности, проведённые из одной точки). Три неизвестных отрезка $p$ , $q$ , $r$ удовлетворяют системе уравнений $\begin{array}{l} p + q - c = 0, \\ q + r - a = 0, \\ r + p - b = 0, \end{array}$ решая которую, находим $\begin{array}{l} p = \frac{1}{2} (b + c - a), \\ q = \frac{1}{2} (c + a - b), \\ r = \frac{1}{2} (a + b - c) . \end{array}$

Эта система уравнений даёт типичный пример системы линейных алгебраических уравнений. Слова «линейных» и «алгебраических» означают, что в левой части уравнения (после переноса всего, что только можно, из правой части в левую) находятся линейные многочлены от неизвестных.

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

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

В общем случае система линейных уравнений имеет следующий вид: $\begin{array}{l} a_{1⁣ 1} x_{1} + a_{1⁣ 2} x_{2} + \dots + a_{1⁣ n} x_{n} + b_{1} = 0 \\ a_{2⁣ 1} x_{1} + a_{2⁣ 2} x_{2} + \dots + a_{2⁣ n} x_{n} + b_{2} = 0 \\ \dots \\ a_{k⁣ 1} x_{1} + a_{k⁣ 2} x_{2} + \dots + a_{k⁣ n} x_{n} + b_{k} = 0 \end{array}$ Она задаётся двумя наборами чисел $a_{i⁣ j}$ и $b_{i}$ ( $i = 1, \dots, k$ , $j = 1, \dots, n$ ). Многие алгоритмы, предназначенные для решения систем линейных уравнений, получают сразу оба набора чисел, то есть изначально знают все уравнения системы. Таковы методы Гаусса и Крамера.

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


Готовая программа		Идеи реализации

Информатика-54© А. Н. Швец