Метод прогонки систем линейных уравнений

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

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

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

f₂(L) = max[f₂ + f₁(L — 2x₂)]; 0 ≤ x₂ ≤ 5; x₂ = 0,1,2,3,4,5.
f₂(0) = max[9+6] = 15
f₂(1) = max[9+7] = 16
f₂(2) = max[9+11, 11+6] = 20
f₂(3) = max[9+12, 11+7] = 21
f₂(4) = max[9+15, 11+11, 13+6] = 24
f₂(5) = max[9+16, 11+12, 13+7] = 25
Таблица 2 – Расчет значения функции f₂(L)

f₃(L) = max[f₃ + f₂(L — 2x₃)]; 0 ≤ x₃ ≤ 5; x₃ = 0,1,2,3,4,5.
f₃(0) = max[8+15] = 23
f₃(1) = max[8+16] = 24
f₃(2) = max[8+20, 12+15] = 28
f₃(3) = max[8+21, 12+16] = 29
f₃(4) = max[8+24, 12+20, 14+15] = 32
f₃(5) = max[8+25, 12+21, 14+16] = 33
Таблица 3 – Расчет значения функции f₃(L)

II этап. Безусловная оптимизация.
Таким образом, максимум f₃(5) = 33
При этом x₃ = 0, так как f₃(5) = 33 достигается при х₃=0 (см. таблицу 3).
Остальные x распределяются следующим образом:
L = 5 — 2 * 0 = 5
f₂(5) = 25 достигается при х₂ = 0 (см. таблицу 2).
L = 5 — 2 * 0 = 5
f₁(5) = 16 достигается при х₁ = 5 (см. таблицу 1).
L = 5 — 1 * 5 = 0
В итоге наилучший вариант достигается при значениях: x₁ = 5, x₂ = 0, x₃ = 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₄ = 6 отданы 4-у предприятию. В этом случае максимальный доход, как это видно из таблицы 1*, составит 0.56, следовательно:
F₄(c₄) = g₄(x₄)
Таблица 1.

Таблица 1*.

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

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

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

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

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

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

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

Пример №3 . Распределите c=200 млн ден. ед. инвестиций между четырьмя министерствами республики ( n=4 ) на реконструкцию и модернизацию производственных мощностей таким образом, чтобы суммарный прирост производства продукции всех министерств f4(с) был максимальным. Прирост выпуска продукции в каждом из министерств gi(x) в зависимости от объема выделенных средств x (0 c=200 млн ден. ед. между первыми тремя министерствами, максимизирующее их суммарный прирост производства продукции f3(с).
Примечание. Основная задача решается с помощью процедуры прямой прогонки. Ответ на подзадачу можно получить из таблицы n-1 исходного решения.

Линейные уравнения. Решение систем линейных уравнений. Метод прогонки.

Метод прогонки (алгоритм Томаса) используют для решения СЛУ типа Ax=F, где A — трёхдиагональная матрица. Это вариант метода последовательного исключения неизвестных.

Система уравнений Ax=F равноценна соотношению:

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

Выразим x_i-1 и x_i через x_i+1, подставим в уравнение, используя это соотношение, (1):

где F_i — правая часть i-го уравнения.

Это соотношение выполняется не завися от решения, если потребовать:

,

,

Получаем из 1-го уравнения:

.

После того, как нашли прогоночные коэффициенты α и β, используем уравнение (2) и получим решение системы. Причем,

.

Еще одним вариантом объяснения смысла метода прогонки является такой вариант: преобразуем уравнение (1) к равнозначному ему уравнению:

c надиагональной (наддиагональной) матрицей:

Рассчеты проводим в 2 этапа. На 1-ом этапе вычисляем компоненты матрицы C′_i и вектора F′, начиная с i=2 до i=n:

На 2-ом этапе, для i=n,n−1,…,1 вычисляем решение:

Для применимости формул метода прогонки достаточно свойства строгого диагонального преобладания у матрицы A.

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

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

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

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

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

• Запись обратного хода в виде , так как преобразованная матрица – двухдиагональная.

•Вывод рекуррентного соотношения для и через и и получение соотношения для и .

• Осуществление обратного хода метода прогонки и определение всех неизвестных.

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

i = 1,2,…, n, (2.6)

Запись (2.6) представляет собой так называемый КАНОНИЧЕСКИЙ ВИД СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДА ПРОГОНКИ. При этом матрица система (2.6) имеет вид

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

(2.7)

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

Подставляя в систему (2.6), получим соотношение

из которого нетрудно получить

Сравнивая это соотношение с (2.7), можем записать рекуррентные соотношения

(2.8)

для вычисления так называемых ПРОГОНОЧНЫХ КОЭФФИЦИЕНТОВ.

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

Для начала прямого хода метода прогонки необходимо задать начальные (стартовые) значения прогоночных коэффициентов, например, Отметим, что, вообще говоря, начальные значения коэффициентов в рассмотренной схеме вычислений не требуются, так как значения коэффициентов вычисляются только через коэффициенты первого уравнения системы (2.6): при i = 1 из (2.6) получаем соотношение Сравнивая это выражение с (2.7) при i =1, получаем а значение в обратном ходе вычисляем по соотношению Использование в качестве начальных значений целесообразно по двум причинам: сохраняется однородность вычислительного алгоритма для всех i = 2, 3, …,n; упрощается обсуждение и доказательство условия корректности и устойчивости метода прогонки. Из того обстоятельства, что коэффициенты не зависят от (в соотношениях(2.8) при i =1 коэффициенты умножаются на ), следует, что можно задать любые значения для прогоночных коэффициентов . Далее будет ясно, почему удобно положить Для начала обратного хода метода прогонки необходимо для вычисления задать значение . Так как , то из первого соотношения (2.8) вытекает, что и, следовательно, можно задать любое значение для Обычно полагают , и тогда

Метод прогонки устойчив, если Метод прогонки корректен, если

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

Из этой формулы при следует, что в данном случае погрешность не возрастает.

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

i = 1,2, …, n.

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

.

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

Для реализации метода требуется примерно 8n операций, из которых 3n составляют операции типа умножения и 5n – операции типа сложения. При численном решении дифференциальных уравнений используются различные варианты метода прогонки: метод встречных прогонок, потоковая прогонка, матричная прогонка для систем векторных уравнений. Отметим, что

Метод прогонки обобщается на случай, при котором в системе (2.6) — квадратные матрицы размерности , а — векторы размерности m. Тогда соотношения (2.7) и (2.8) метода прогонки, в которых все действия совершаются уже над матрицами, а не над скалярами, сохраняются, а в (2.8) является соответствующей обратной матрицей.

Условие устойчивости матричной прогонки выглядит как , а условие корректности и устойчивости имеет вид .

Дата добавления: 2015-11-06 ; просмотров: 2629 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ