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

Уравнение прямой для двумерного и трехмерного пространств

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

Прямая представляет собой совокупность точек, каждую из которых можно получить из предыдущей с помощью переноса на параллельные друг другу вектора. Например, имеется точка M и N. Соединяющий их вектор MN¯ переводит M в N. Имеется также третья точка P. Если вектор MP¯ или NP¯ параллелен MN¯, тогда все три точки на одной прямой лежат и образуют ее.

В зависимости от размерности пространства уравнение, задающее прямую, может изменять свою форму. Так, всем известная линейная зависимость координаты y от x в пространстве описывает плоскость, которая параллельна третьей оси z. В связи с этим в данной статье будем рассматривать только векторное уравнение для прямой. Оно имеет одинаковый вид для плоскости и трехмерного пространства.

В пространстве прямую можно задать следующим выражением:

(x; y; z) = (x 0 ; y 0 ; z 0) + α*(a; b; c)

Здесь значения координат с нулевыми индексами соответствуют принадлежащей прямой некоторой точки, u¯(a; b; c) - координаты направляющего вектора, который лежит на данной прямой, α - произвольное действительное число, изменяя которое можно получить все точки прямой. Это уравнение называется векторным.

Часто приведенное уравнение записывают в раскрытом виде:

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

(x; y) = (x 0 ; y 0) + α*(a; b);

Уравнение плоскости

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

Предположим, что точка M(x 0 ; y 0 ; z 0) плоскости принадлежит, а вектор n¯(A; B; C) ей перпендикулярен, тогда для всех точек (x; y; z) плоскости справедливым будет равенство:

A*x + B*y + C*z + D = 0, где D = -1*(A*x 0 + B*y 0 + C*z 0)

Следует запомнить, что в этом общем уравнении плоскости коэффициенты A, B и C являются координатами нормального к плоскости вектора.

Расчет расстояний по координатам

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

Пусть имеются две пространственные точки:

A 1 (x 1 ; y 1 ; z 1) и A 2 (x 2 ; y 2 ; z 2)

Тогда дистанция между ними вычисляется по формуле:

A 1 A 2 = √((x 2 -x 1) 2 +(y 2 -y 1) 2 +(z 2 -z 1) 2)

С помощью этого выражения также определяют длину вектора A 1 A 2 ¯.

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

A 1 A 2 = √((x 2 -x 1) 2 +(y 2 -y 1) 2)

Теперь рассмотрим различные случаи проекции на плоскости точки на прямую и на плоскость в пространстве.

Точка, прямая и расстояние между ними

Предположим, что имеется некоторая точка и прямая:

P 2 (x 1 ; y 1);

(x; y) = (x 0 ; y 0) + α*(a; b)

Расстояние между этими геометрическими объектами будет соответствовать длине вектора, начало которого лежит в точке P 2 , а конец находится в такой точке P на указанной прямой, для которой вектор P 2 P ¯ этой прямой перпендикулярен. Точка P называется проекцией точки P 2 на рассматриваемую прямую.

Ниже приведен рисунок, на котором изображена точка P 2 , ее расстояние d до прямой, а также вектор направляющий v 1 ¯. Также на прямой выбрана произвольная точка P 1 и от нее до P 2 проведен вектор. Точка P здесь совпадает с местом, где перпендикуляр пересекает прямую.

Видно, что оранжевые и красные стрелки образуют параллелограмм, сторонами которого являются вектора P 1 P 2 ¯ и v 1 ¯, а высотой - d. Из геометрии известно, что для нахождения высоты параллелограмма следует разделить его площадь на длину основания, на которое опущен перпендикуляр. Поскольку площадь параллелограмма вычисляется как векторное произведение его сторон, то получаем формулу для расчета d:

d = ||/|v 1 ¯|

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

Решить эту задачу можно было бы иначе. Для этого следует записать два уравнения:

• скалярное произведение P 2 P ¯ на v 1 ¯ должно равняться нулю, поскольку эти вектора взаимно перпендикулярны;
• координаты точки P должны удовлетворять уравнению прямой.

Этих уравнений достаточно, чтобы найти координаты P, а затем и длину d по формуле, приведенной в предыдущем пункте.

Задача на нахождение дистанции между прямой и точкой

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

(x; y) = (3; 1) - α*(0; 2)

Необходимо найти точки проекции на прямую на плоскости, а также расстояние от M до прямой.

Обозначим проекцию, которую следует найти, точкой M 1 (x 1 ; y 1). Решим эту задачу двумя способами, описанными в предыдущем пункте.

Способ 1. Направляющий вектор v 1 ¯ координаты имеет (0; 2). Чтобы построить параллелограмм, выберем принадлежащую прямой какую-нибудь точку. Например, точку с координатами (3; 1). Тогда вектор второй стороны параллелограмма будет иметь координаты:

(5; -3) - (3; 1) = (2; -4)

Теперь следует вычислить произведение векторов, задающих стороны параллелограмма:

Подставляем это значение в формулу, получаем расстояние d от M до прямой:

Способ 2. Теперь найдем другим способом не только расстояние, но и координаты проекции M на прямую, как это требует условие задачи. Как было сказано выше, для решения задачи необходимо составить систему уравнений. Она примет вид:

(x 1 -5)*0+(y 1 +3)*2 = 0;

(x 1 ; y 1) = (3; 1)-α*(0; 2)

Решаем эту систему:

Проекция исходной точки координаты имеет M 1 (3; -3). Тогда искомое расстояние равно:

d = |MM 1 ¯| = √(4+0) = 2

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

Проекция точки на плоскость

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

Предположим, что проекция на плоскость точки М координаты имеет следующие:

Сама плоскость описывается уравнением:

A*x + B*y + C*z + D = 0

Исходя из этих данных, мы можем составить уравнение прямой, пересекающей плоскость под прямым углом и проходящей через M и M 1:

(x; y; z) = (x 0 ; y 0 ; z 0) + α*(A; B; C)

Здесь переменные с нулевыми индексами - координаты точки M. Рассчитать положение на плоскости точки M 1 можно исходя из того, что ее координаты должны удовлетворять обоим записанным уравнениям. Если этих уравнений при решении задачи будет недостаточно, то можно использовать условие параллельности MM 1 ¯ и вектора направляющего для заданной плоскости.

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

Задача с точкой и плоскостью

Пусть дана точка M(1; -1; 3) и плоскость, которая описывается следующим общим уравнением:

Следует вычислить координаты проекции на плоскость точки и рассчитать расстояние между этими геометрическими объектами.

Для начала построим уравнение прямой, проходящей через М и перпендикулярной указанной плоскости. Оно имеет вид:

(x; y; z) = (1; -1; 3) + α*(-1; 3; -2)

Обозначим точку, где эта прямая пересекает плоскость, M 1 . Равенства для плоскости и прямой должны выполняться, если в них подставить координаты M 1 . Записывая в явном виде уравнение прямой, получаем следующие четыре равенства:

X 1 + 3*y 1 -2*z 1 + 4 = 0;

y 1 = -1 + 3*α;

Из последнего равенства получим параметр α, затем подставим его в предпоследнее и во второе выражение, получаем:

y 1 = -1 + 3*(3-z 1)/2 = -3/2*z 1 + 3,5;

x 1 = 1 - (3-z 1)/2 = 1/2*z 1 - 1/2

Выражение для y 1 и x 1 подставим в уравнение для плоскости, имеем:

1*(1/2*z 1 - 1/2) + 3*(-3/2*z 1 + 3,5) -2*z 1 + 4 = 0

Откуда получаем:

y 1 = -3/2*15/7 + 3,5 = 2/7;

x 1 = 1/2*15/7 - 1/2 = 4/7

Мы определили, что проекция точки M на заданную плоскость соответствует координатам (4/7; 2/7; 15/7).

Теперь рассчитаем расстояние |MM 1 ¯|. Координаты соответствующего вектора равны:

MM 1 ¯(-3/7; 9/7; -6/7)

Искомое расстояние равно:

d = |MM 1 ¯| = √126/7 ≈ 1,6

Три точки проекции

Во время изготовления чертежей часто приходится получать проекции сечений на взаимно перпендикулярные три плоскости. Поэтому полезно рассмотреть, чему будут равны проекции некоторой точки M с координатами (x 0 ; y 0 ; z 0) на три координатные плоскости.

Не сложно показать, что плоскость xy описывается уравнением z = 0, плоскость xz соответствует выражению y = 0, а оставшаяся плоскость yz обозначается равенством x = 0. Нетрудно догадаться, что проекции точки на 3 плоскости будут равны:

для x = 0: (0; y 0 ; z 0);

для y = 0: (x 0 ; 0 ; z 0);

для z = 0: (x 0 ; y 0 ; 0)

Где важно знать проекции точки и ее расстояния до плоскостей?

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

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

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

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

Количество объектов 2 3 4 5 6 7 8 9 10 Количество вариантов 2 3 4 5 6 7 8 9 10

Пример №1 . Решить задачу методом динамического программирования в прямом и обратном времени для целевой функции, заданной таблично.
F(x 1 ,x 2 ,x 3) = f 1 (x 1) + f 2 (x 2) + f 3 (x 3) → max
x 1 + 2x 2 + 2x 3 ≤ 5

X	0	1	2	3	4	5
f 1 (x 1)	6	7	11	12	15	16
f 2 (x 2)	9	11	13	15
f 3 (x 3)	8	12	14	16

Решение.
I этап. Условная оптимизация . f 1 (L) = max(f 1); 0 ≤ x 1 ≤ 5; x 1 = 0,1,2,3,4,5.
f 1 (0) = max = 6
f 1 (1) = max = 7
f 1 (2) = max = 11
f 1 (3) = max = 12
f 1 (4) = max = 15
f 1 (5) = max = 16
Таблица 1 – Расчет значения функции f 1 (L)

L	0	1	2	3	4	5
f 1 (L)	6	7	11	12	15	16
x 1	0	1	2	3	4	5

f 2 (L) = max; 0 ≤ x 2 ≤ 5; x 2 = 0,1,2,3,4,5.
f 2 (0) = max = 15
f 2 (1) = max = 16
f 2 (2) = max = 20
f 2 (3) = max = 21
f 2 (4) = max = 24
f 2 (5) = max = 25
Таблица 2 – Расчет значения функции f 2 (L)

L	0	1	2	3	4	5
f 2 (L)	15	16	20	21	24	25
x 2	0	0	0	0	0	0

f 3 (L) = max; 0 ≤ x 3 ≤ 5; x 3 = 0,1,2,3,4,5.
f 3 (0) = max = 23
f 3 (1) = max = 24
f 3 (2) = max = 28
f 3 (3) = max = 29
f 3 (4) = max = 32
f 3 (5) = max = 33
Таблица 3 – Расчет значения функции f 3 (L)

L	0	1	2	3	4	5
f 3 (L)	23	24	28	29	32	33
x 3	0	0	0	0	0	0

II этап. Безусловная оптимизация .
Таким образом, максимум f 3 (5) = 33
При этом x 3 = 0, так как f 3 (5) = 33 достигается при х 3 =0 (см. таблицу 3).
Остальные x распределяются следующим образом:
L = 5 - 2 * 0 = 5
f 2 (5) = 25 достигается при х 2 = 0 (см. таблицу 2).
L = 5 - 2 * 0 = 5
f 1 (5) = 16 достигается при х 1 = 5 (см. таблицу 1).
L = 5 - 1 * 5 = 0
В итоге наилучший вариант достигается при значениях: x 1 = 5, x 2 = 0, x 3 = 0

Пример №2 . Рассмотрим задачу об оптимальном размещении капитала K = nh в m различных независимых фондах (банки, организации, фирма и т.д.), для которых известна ожидаемая прибыль f i при капиталовложениях x i = ih, i = 1..n. Здесь n – количество дискретных приращений h (дискрет), на которые разбит капитал К.
Пусть такие данные имеются по четырем (m=4) фондам для h = 1 млн. руб., n = 6

Решение.
I этап. Условная оптимизация.
1-й шаг: k = 4.
Предположим, что все средства в количестве x 4 = 6 отданы 4-у предприятию. В этом случае максимальный доход, как это видно из таблицы 1*, составит 0.56, следовательно:
F 4 (c 4) = g 4 (x 4)
Таблица 1.

0	x 1	0	1	2	3	4	5	6
x 4	f 0 (x 0) / F 4 (x 4)	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
1	0.2	0	0	0	0	0	0.2	0
2	0.33	0	0	0	0	0.33	0	0
3	0.42	0	0	0	0.42	0	0	0
4	0.48	0	0	0.48	0	0	0	0
5	0.53	0	0.53	0	0	0	0	0
6	0.56	0.56*	0	0	0	0	0	0

Таблица 1*.

c 1	0	1	2	3	4	5	6
F 0 (c 1)	0	0.2	0.33	0.42	0.48	0.53	0.56
x 1	0	1	2	3	4	5	6

2-й шаг: k = 3.

F 3 (c 3) = max [ g 3 (x 3) + F 4 (c 3 - x 3)]
Таблица 2.

0	x 2	0	1	2	3	4	5	6
x 3	f 3 (x 3) / F 3 (x 3)	0	0.2	0.33	0.42	0.48	0.53	0.56
0	0	0	0.2*	0.33	0.42	0.48	0.53	0.56
1	0.15	0.15	0.35*	0.48*	0.57	0.63	0.68	0
2	0.25	0.25	0.45	0.58	0.67	0.73	0	0
3	0.4	0.4	0.6*	0.73*	0.82	0	0	0
4	0.5	0.5	0.7	0.83*	0	0	0	0
5	0.62	0.62	0.82	0	0	0	0	0
6	0.73	0.73	0	0	0	0	0	0

Заполняем таблицу 2*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x 2 .
Таблица 2*.

c 2	0	1	2	3	4	5	6
F 3 (c 2)	0	0.2	0.35	0.48	0.6	0.73	0.83
x 2	0	0	1	1	3	3	4

3-й шаг: k = 2.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F 2 (c 2) = max [ g 2 (x 2) + F 3 (c 2 - x 2)]
Таблица 3.

0	x 3	0	1	2	3	4	5	6
x 2	f 4 (x 4) / F 2 (x 2)	0	0.2	0.35	0.48	0.6	0.73	0.83
0	0	0	0.2	0.35	0.48	0.6	0.73	0.83
1	0.25	0.25*	0.45*	0.6	0.73	0.85	0.98	0
2	0.41	0.41	0.61*	0.76*	0.89	1.01	0	0
3	0.55	0.55	0.75	0.9*	1.03*	0	0	0
4	0.65	0.65	0.85	1	0	0	0	0
5	0.75	0.75	0.95	0	0	0	0	0
6	0.8	0.8	0	0	0	0	0	0

Заполняем таблицу 3*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x 3 .
Таблица 3*.

c 3	0	1	2	3	4	5	6
F 4 (c 3)	0	0.25	0.45	0.61	0.76	0.9	1.03
x 3	0	1	1	2	2	3	3

4-й шаг: k = 1.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F 1 (c 1) = max [ g 1 (x 1) + F 2 (c 1 - x 1)]
Таблица 4.

0	x 4	0	1	2	3	4	5	6
x 1	f 5 (x 5) / F 1 (x 1)	0	0.25	0.45	0.61	0.76	0.9	1.03
0	0	0	0.25	0.45	0.61	0.76	0.9	1.03
1	0.28	0.28*	0.53*	0.73*	0.89	1.04	1.18	0
2	0.45	0.45	0.7	0.9	1.06	1.21	0	0
3	0.65	0.65	0.9*	1.1*	1.26*	0	0	0
4	0.78	0.78	1.03	1.23	0	0	0	0
5	0.9	0.9	1.15	0	0	0	0	0
6	1.02	1.02	0	0	0	0	0	0

Заполняем таблицу 4*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x 4 .
Таблица 4*.

c 4	0	1	2	3	4	5	6
F 5 (c 4)	0	0.28	0.53	0.73	0.9	1.1	1.26
x 4	0	1	1	1	3	3	3

II этап. Безусловная оптимизация.
1-й шаг: k = 1.
По данным таблицы 4* максимальный доход при распределении 6 между предприятиями составляет c 1 = 6, F 1 (6) = 1.26. При этом 1-му предприятию нужно выделить x 1 = 3.
2-й шаг: k = 2.

c 2 = c 1 - x 1 = 6 - 3 = 3.
По данным таблицы 3* максимальный доход при распределении 3 между предприятиями составляет c 2 = 3, F 2 (3) = 0.61. При этом 2-му предприятию нужно выделить x 2 = 2.
3-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c 3 = c 2 - x 2 = 3 - 2 = 1.
По данным таблицы 2* максимальный доход при распределении 1 между предприятиями составляет c 3 = 1, F 3 (1) = 0.2. При этом 3-му предприятию нужно выделить x 3 = 0.
4-й шаг: k = 4.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c 4 = c 3 - x 3 = 1 - 0 = 1.
По данным таблицы 1* максимальный доход при распределении 1 между предприятиями составляет c 4 = 1, F 4 (1) = 0.20. При этом 4-му предприятию нужно выделить x 4 = 1.
Таким образом, оптимальный план инвестирования предприятия:
x 1 = 3
x 2 = 2
x 3 = 0
x 4 = 1
который обеспечит максимальный доход, равный: F(6) = g 1 (3) + g 2 (2) + g 3 (0) + g 4 (1) = 0.65 + 0.41 + 0 + 0.20 = 1.26.

Численные методы линейной алгебры

3. Метод прогонки

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

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

Преобразуем первое уравнение системы (8) к виду x 1 = 1 x 2 + 1 , где

1 = -с 1 / b 1 и 1 = -d 1 / b 1 . Подставим полученное для x 1 выражение во второе уравнение системы (8)

a 2 (1 x 2 + 1) + b 2 x 2 + c 2 x 3 = d 2 .

Представим это уравнение в виде x 2 = 2 x 3 + 2 , где 2 = -с 2 / (b 2 + a 2 1) и 2 = (d 2 - a 2 1) / (b 2 + a 2 1). Полученное для x 2 выражение подставим в третье уравнение системы (8) и т.д.

На i-м шаге (1 < i < n) процесса i-е уравнение системы принимает вид

x i = i x i+1 + i , (9)

где i = -с i / (b i + a i i-1) и i = (d i - a i i-1) / (b i + a i i-1).

На последнем n-м шаге подстановка в последнее уравнение системы (8) выражения x n -1 = n -1 x n + n -1 дает уравнение a n (n -1 x n + n -1) + b n x n = d n , из которого можно определить значение x n = n = (d n - a n n-1) / (b n + a n n-1).

Значения остальных неизвестных x i (i = n-1, n-2, ..., 1) легко вычисляются по формуле (9).

Таким образом, алгоритм прогонки, подобно методу Гаусса, включает два этапа - прямой ход (прямая прогонка) и обратный ход (обратная прогонка).

Прямой ход метода прогонки состоит в вычислении прогоночных коэффициентов

i (i =) и i (i =).

При i = 1 эти коэффициенты вычисляются по формулам:

1 = -с 1 / 1 ; 1 = -d 1 / 1 ; 1 = b 1 .

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

i = -с i / i ; i = (d i - a i i-1) / i ; i = b i + a i i-1 .

Прямая прогонка завершается при i = n:

n = (d n - a n n-1) / n ; n = b n + a n n-1 .

Обратный ход метода прогонки позволяет вычислить значения неизвестных. Сначала полагают x n = n . Затем в обратном порядке по формуле (9) определяют значения неизвестных x n -1 , x n -2 , ..., x 1 .

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

Теорема . Пусть коэффициенты системы (8) удовлетворяют следующим неравенствам

b k a k +c k ; b k >a k ; k = , где a 1 = 0; b n = 0. Тогда i 0 и i

1 для всех i =

Заметим, что при всех i 0 вычисления по формулам прямой прогонки могут быть доведены до конца (ни один из знаменателей не обратится в нуль). Одновременно все коэффициенты i , такие, что i 1, обеспечивают устойчивость по входным данным этапа обратной прогонки по формуле (9).

Вычислительная математика

Метод деления отрезка пополам является самым простым и надежным способом решения нелинейного уравнения. Пусть из предварительного анализа известно, что корень уравнения (2.1) находится на отрезке , т. е. x*, так, что f(x*) = 0...

Вычислительная математика

Метод Ньютона является наиболее эффективным методом решения нелинейных уравнений. Пусть корень x* , так, что f(a)f(b) < 0. Предполагаем, что функция f(x) непрерывна на отрезке и дважды непрерывно дифференцируема на интервале (a, b). Положим x0 = b...

Вычислительная математика

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

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

Линейное и нелинейное программирование

Итерация 1. Счет итераций k = 0 Итерация 2. Счет итераций k = 1 Поиск завершен 3.3...

Математическое моделирование и численные методы в решении технических задач

Теоретические сведения. Решить дифференциальное уравнение у/=f(x,y) численным методом - это значит для заданной последовательности аргументов х0, х1…, хn и числа у0, не определяя функцию у=F(x), найти такие значения у1, у2,…, уn, что уi=F(xi)(i=1,2,…, n) и F(x0)=y0...

Математическое моделирование при активном эксперименте

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

Математическое программирование

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) -- это итерационный численный метод нахождения корня (нуля) заданной функции. Чтобы численно решить уравнение f(x)=0 методом простой итерации...

Метод вращений решения СЛАУ

Метод геометрических преобразований при решении геометрических задач на построение

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

Решение параболических уравнений

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

Система дифференциальных уравнений с постоянными коэффициентами

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

Системный анализ групп преобразований состояний кубика Рубика

CFOP - это название четырёх стадий сборки(рисунок 3.2): Cross, F2L, OLL, PLL: 1) Cross - сборка креста...

Численные методы линейной алгебры

Метод прогонки представляет собой простой и эффективный алгоритм решения систем линейных алгебраических уравнений с трехдиагональными матрицами коэффициентов следующего вида (8) Системы такого вида часто возникают при решении различных...

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

Пусть уравнение (1) имеет корень на отрезке , причем f (x) и f "(x) непрерывны и сохраняют постоянные знаки на всем интервале . Геометрический смысл метода Ньютона состоит в том, что дуга кривой y = f(x) заменяется касательной...

Данный метод также является модификацией метода Гаусса для частного случая разреженных систем - систем с матрицей трехдиагонального типа (краевая задача ДУ).

Каноническая форма их записи

(1.6)

или в развернутом виде:

(1.7)

При этом, как правило, все коэффициенты b i  0.

Метод реализуется в два этапа - прямым и обратным ходами.

Прямой ход . Каждое неизвестное x i выражается через x i +1

(x i = A i  x i +1 + B i для i = 1,2, ..., n – 1) (1.8)

посредством прогоночных коэффициентов A i и B i . Определим алгоритм их вычисления.

Из первого уравнения системы (1.7) находим x 1:

.

Из уравнения (1.8) при i = 1 x 1 = A 1  x 2 + B 1 . Следовательно,

и согласно уравнению (1.8) при i = 2 x 2 = A 2 x 3 + B 2 , следовательно:

,

где е 2 = а 2 А 1 + b 2 .

Ориентируясь на соотношения индексов при коэффициентах уравнений (1.9) и (1.9*), можно получить эти соотношения для общего случая:

,

где е i = а i  А i –1 + b i (i = 2,3, ..., n – 1) . (1.10)

Обратный ход. Из последнего уравнения системы (1.7) с использованием данных выражения (1.8) при i = n – 1

.

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

(1.12)

или хотя бы для одного b i имеет место строгое неравенство (1.12), деление на «0» исключается и система имеет единственное решение.

Заметим, что условие (1.12) является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем (1.7) метод прогонки может быть устойчивым и при несоблюдении условия (1.12).

Схема алгоритма метода прогонки может иметь вид, представленный на рисунке 1.2.

Рисунок 1.2 - Блок-схема метода прогонки

Итерационные методы решения слау

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

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

Для применения метода итераций исходную систему необходимо привести к итерационному виду

(1.13)

и затем итерационный процесс выполнить по рекуррентным формулам:

, k = 0, 1, 2, ... . (1.13*)

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

Для сходимости метода (1.13*) необходимо и достаточно, чтобы | i (G )| < 1, где  i (G ) - все собственные значения матрицы G . Сходимость будет и в случае, если ||G || < 1, ибо | i (G )| <  ||G || ( - любой).

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

||G || =
или ||G || =
, (1.14)

где
. Сходимость гарантирована также, если исходная матрицаА имеет диагональное преобладание, т. е.

. (1.15)

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

Если выполняется условие (1.15), тогда преобразование к итерационному виду (1.13) можно осуществить просто, решая каждое i -е уравнение системы (1) относительно x i по следующим рекуррентным формулам:

g ij = − a ij / a ii ; g ii = 0; f i = b i / a ii , (1.15*)

т. е.
.

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