Научная литература
booksshare.net -> Добавить материал -> Математика -> Боглаев Ю.П. -> "Вычислительная математика и программирование " -> 107

Вычислительная математика и программирование - Боглаев Ю.П.

Боглаев Ю.П. Вычислительная математика и программирование — Высшая школа, 1990. — 546 c.
ISBN 5-06-00623-9
Скачать (прямая ссылка): vychmatiprog1990.djvu
Предыдущая << 1 .. 101 102 103 104 105 106 < 107 > 108 109 110 111 112 113 .. 168 >> Следующая

(8.4.9). Рассматриваемый здесь ?i^-алгоритм дает последовательность матриц А(к) почти треугольного вида (8.4.1) таких, что
lim a$-ia$i,i = 0.
к—*-oo
Когда сходящиеся к нулю поддиагональные элементы матриц А{к) будут иметь величину меньше заданной точности, (^-алгоритм завершается.
Каждый шаг QR алгоритма состоит в переходе от матрицы А(к) к матрице А(к+1\ к = 0, 1, ..., А(0) = А по следующему правилу.
1. Матрица А{к) разлагается в произведение ортогональной
и треугольной матриц
A(k) = Q(k)R{k) (8.4.10)
по схеме (8.4.3).
2. Матрица А{к+1) определяется перестановкой сомножителей в (8.4.10): '
Л<*+1> = Я<*>6(*>, к = 0, 1, 2, ... (8.4.11)
333
Из (8.4.10) определим
Отсюда
или
A* + V = (QM)-'A{k)Q{k\
Л»+1> = (е«)-1 ... (QW)-'AQ<0) ... Q(k\
Обозначим P(k) = Q(0) ... Q(k). Тогда gR-алгоритм можно записать в форме
Это соотношение указывает, что собственные значения матриц А(к) и А совпадают.
Сформулируем утверждение о сходимости (?К алгоритма.
Теорема 8Л0. Пусть матрица А невырождена, имеет различные собственные значения Хь 1 < / ^ п, модули \ Х( | которых, за исключением комплексно-сопряженных, также различны и упорядочены в порядке, невозрастания, тогда при к-юо
8.4.5. Применение библиотечных программ. Рассмотрим следующую задачу: определить собственные значения матрицы
Матрица А—симметричная, поэтому для решения поставленной задачи применяется программа В0А0:
REAL A(3,3),G(3),W(3)
INTEGER K,N,I
DATA A/1.,2.,3.,2.,4.,5.,3.,5.,6./
DATA K,N,I/3,3,0/
С ОБРАЩЕНИЕ К ПРОГРАММЕ В0А0
CALL ВОА0(А, К, N, G, W, I)
С ВЫВОД НА ТЕРМИНАЛ
WRITE (5,1) G 1 FORMAT (2X,3E13.6)
END
Рассмотрим задачу определения собственных значений и собственных векторов матрицы А:
А{к+1) = (Р{к))~1АР(к).
Для ее решения применим программу ВО АЗ:
334
\
ч
V
REAL A(3,3),G1(3),G2(3),X1(3,3),X2(3,3)
INTEGER K,N,L1,L2,J(3),I DATA A/1.,4.,7.,2.,5.,8.,3.,6.,9./
DATA K,N,Ll,L2,I/3,3,3,3,0/
С ОБРАЩЕНИЕ К ПРОГРАММЕ ВОАЗ
CALL B0A3(A,K,N,G1,G2,X1,L1,X2,L2,J,I)
С ВЫВОД НА ТЕРМИНАЛ СОБСТВЕННЫХ ЗНАЧЕНИЙ
WRITE (5,1) (G(I),G2(I),1 = 1,3)
1 FORMAT (2X,'RE',E13.6,2X,'IM',E13.6)
С ВЫВОД НА ТЕРМИНАЛ СОБСТВЕННЫХ ВЕКТОРОВ
WRITE (5,2) ((X(J,I),X2(J,I),J= 1,3)1= 1,3)
2 FORMAT (2Х,El3.6,2Х,El 3.6)
END
• 8.5. Линейная оптимизация
Рассмотрим задачи, которые в математической литературе обычно называют линейным программированием. Термин «линейное программирование» появился до широкого использования ЭВМ и в этой книге не употребляется из-за его несоответствия современному пониманию смысла программирования.
8.5.1. Постановка канонической задачи. Каноническая задача линейной оптимизации формулируется следующим образом: найти вектор х = (хх, ..., х„), доставляющий
ттФ(х) = с1х1-|-С2*2 + ... +спхп ("8.5.1)
при условиях
«1.1*1+«1,2*2+ - +«1.п*» = *1> /8 5 2)
«2.1*1+«2.2*2+-+«2,и*1« = *2>
«m,l*l+«m,2*2+ ••• +ат,пХп = Ьт,
х*^0, l^i^n, bj^0, 1</<т. (8.5.3)
Задача (8.5.1) — (8.5.3) сокращенно записывается в матрично-векторной форме так:
min (с, х),
Ах = Ь, (8.5.4)
х^О, О,
где вещественные матрица Л = (яи), векторы ci9 1<у<т,
заданы; строки матрицы А линейно независимы, откуда, в частности, следует т^п. Неотрицательность элементов вектора Ъ легко получить, умножив, если это необходимо, соответствующие неравенства в (8.5.2) на —1.
В общей постановке задача линейной оптимизации может не иметь каноническую форму. Однако, как будет показано ниже, введением дополнительных переменных в вектор х каждая задача сводится к канонической.
335
Функция Ф(х) называется целевой функцией задачи, система
(8.5.2), (8.5.3) — системой ограничений.
В общей постановке задачи линейной оптимизации, возможно, ищется максимум целевой функции шахФ(лг). Тогда замена целевой функции на — Ф(х) сводит исходную задачу к минимизации шт(-Ф(х)). Кроме того, в соотношениях типа (8.5.2) могут присутствовать неравенства, например условие
а1х1+а2х2+ ... +апхп ^Ъ
или
а1х1+а2х2 + ... +апхп ^Ъ.
Тогда каждое йеравенство можно заменить двумя соотношениями вида
• а1х1+а2х2+... +апхп+хп+1 = Ь,
хп+1>0,
или
а1х1-\-а2х2+... +апхп-хп+2 = Ь,
Хп + 2
целевую функцию—записать в форме
Ф(х) = сх Хх + ... + Х„+ 0хп + ! + 0*„ + 2
и таким образом привести общую задачу линейной оптимизации к каноническому виду.
8.5.2. Примерьгзадач линейной оптимизации. Следующая задача об определении максимальной прибыли производства является типичной задачей линейной оптимизации. Пусть для изготовления п видов продукции в количестве х19 х2, ..., хп расходуется т видов сырья. Расход сырья /-го вида на единицу у-го вида продукции равен аир запас сырья /-го вида ограничен величиной Ъ{. Каждая единица продукции /-го вида дает прибыль с{ руб. Задача поиска вектора х = (х19 ..., д:„)—количества продукции каждого вида, дающего максимальную прибыль,—принимает следующую форму: найти х, доставляющий
тахФ(х) = с1х1Н-с2х2Н-... +спхп
при ограничениях
п
^=1
х<^0, 1</^л.
Таким образом получили задачу линейной оптимизации, которая введением дополнительных переменных легко приводится к канонической форме.
Предыдущая << 1 .. 101 102 103 104 105 106 < 107 > 108 109 110 111 112 113 .. 168 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed