Форум по математика Планета за помощ по математика

Дискусии и решаване на проблеми по математика, физика, химия, икономика

Часова зона: UTC + 3 часа [лятно часово време]

Въведение в анализа

Теория на опашките (QS)

Резултатите, получени в предишните лекции, могат да бъдат разширени до системи с линейни уравнения на формата

където всички елементи [математика] a_,

1 \ leqslant i \ leqslant n,

1 \ leqslant j \ leqslant n [/ math] и [math] b_i, 1 \ leqslant i \ leqslant n [/ math], са елементи на някакъв затворен полуколектор и ние говорим за решението на системата (3.16) в това полуколко.

За да направим това, нека разгледаме множеството [math] \ mathbb _ (\ mathcal) [/ math] от правоъгълни матрици от тип [math] m \ times n [/ math] с елементи от произволно идемпотентно полукопиране [math] \ mathcal = (S, +, \ cdot, \ bold, \ bold) [/ math]. Наборът от всички квадратни матрици от порядък [math] n [/ math] с елементи от полукорене [math] \ mathcal [/ math] ще се обозначава с [math] \ mathbb_n (\ mathcal) [/ math]. С [math] \ mathsf (\ mathcal) [/ math] обозначаваме множеството от всички матрици от всякакъв тип с елементи от [math] \ mathcal [/ math] .

Операциите на събиране и умножение на матрици се дефинират по абсолютно същия начин, както в числовия случай, като се отчита фактът, че добавянето и умножението на матрични елементи се разбират по смисъла на даден идемпотентен полукопиращ [math] \ mathcal [/ математика], а именно:

1) сумата от матрици [math] A = (a _) [/ math] и [math] B = (b _) [/ math] от тип [math] m \ times n [/ math] се нарича матрица [math] C = (c_) [/ math] от същия тип с [math] елементи c_ = a_ + b _, [/ math] [math] i = \ overline,

j = \ overline [/ math] и използвайте обозначението [math] C = A + B [/ math];

2) произведението [math] AB [/ math] на матрици [math] A = (a _) [/ math] от тип [math] m \ times n [/ math] и [math] B = (b _) [/ math] от тип [math] m \ times p [/ math] е матрица [math] C = (c _) [/ math] от тип [math] m \ times p [/ math] с елементи

Нулевите [math] (O) [/ math] и unit [math] (E) [/ math] матрици от произволен ред се дефинират като се използват единица и нула на полуколелото.

На множеството [math] \ mathbb_n (\ mathcal) [/ math] на всички квадратни матрици с фиксиран ред [math] n [/ math], можете да дефинирате алгебрата

Теорема 3.8. Алгебрата [math] \ mathsf_n (\ mathcal) [/ math] е идемпотентно полукопиране. Ако полукоренето [math] \ mathcal [/ math] е затворено, тогава semiring [math] \ mathsf_n (\ mathcal) [/ math] също е затворено.

Операциите на сумата и произведението на матриците са дефинирани по такъв начин, че всички свойства на операциите на събиране и умножение в полукопче се запазват за съответните операции върху матрици. Следователно аксиомите за полукопиране са валидни за сумата и произведението на матрици от [math] \ mathsf_n (\ mathcal) [/ math] и освен това операцията по добавяне на матрици е идемпотентна. Следователно, [math] \ mathsf_n (\ mathcal) [/ math] е идемпотентен полукорот.

Нека изясним значението на релацията на реда в това идемпотентно полукопиране. По дефиницията на естествения ред на идемпотентно полуколене, неравенството [math] A \ leqslant B [/ math] за матриците [math] A [/ math] и [math] B [/ math] означава, че [math] A + B = B [/ math], или за всички [math] i, \, j [/ math], [math] a_ + b_ = c _ [/ math]. Следователно, [math] A \ leqslant B [/ math] тогава и само ако за всички [math] i, \, j [/ math] [math] a_ \ leqslant b _ [/ math] .

Нека [math] \ mathcal [/ math] е затворен полуколектор. Нека докажем затвореността на идемпотентното полукопиране [math] \ mathsf_n (\ mathcal) [/ math] и съществуването на точен супремум за всяка последователност от матрици в [math] \ mathsf_n (\ mathcal) [/ math] .

Нека [math] \ _> [/ math] е произволна последователност от квадратни матрици [math] A_m = (a_ ^ m) [/ math] от порядък [math] n [/ math]. Помислете за матрицата [math] \ textstyle> a _ ^ \ Bigr)> [/ math]. Всеки елемент [math] \ textstyle = \ sum \ limit_> a _ ^> [/ math] на тази матрица е точната горна граница на поредицата от елементи [math] a _ ^ [/ math]. Тези точни горни граници съществуват, защото [math] a _ ^ [/ math] са членове на затвореното полукопиране [math] \ mathcal [/ math]. Тъй като добавянето на матрици и съотношението на реда в полукопирането на матрици са дефинирани по елемент, матрицата [math] B [/ math] ще бъде точната горна граница на последователността на матриците [math] A_m [/ math] .

Нека сега докажем непрекъснатостта на умножението в [math] \ mathsf_n (\ mathcal) [/ math], т.е. че за всяка последователност [math] \ _> [/ math] на матрици и произволна матрица [math] B [/ math]

Матрицата [math] \ textstyle) = \ sum A_m> [/ math] е точната горна граница на последователността [math] \ _> [/ math]. Тогава имаме

Елементът [math] c _ [/ math] е точната горна граница на последователността [math] \ ^ \> _> [/ math] на елементи от матриците [math] A_m [/ math], т.е.

Използвайки непрекъснатостта на умножението в оригиналното полукопиране [math] \ mathcal [/ math], получаваме

Използвайки непрекъснатостта на добавяне, получаваме

По същия начин се доказва, че [math] \ textstyle [/ math] .

Полуматрична матрица

Полукоренето [math] \ mathsf_n (\ mathcal) [/ math] ще се нарича полукопиране на матрици над полуколенето [math] \ mathcal [/ math]. Доказаната теорема ни позволява да приложим теорема 3.7 към затворени полукольца на матрици върху някои затворени полукольца [math] \ mathcal [/ math] и да решим произволни уравнения на формата (по отношение на неизвестната матрица [math] X [/ math] ):

съответно, където [math] A ^ [/ math] е итерация на матрицата [math] A [/ math] в [math] \ mathsf_n (\ mathcal) [/ math]. Итерацията [math] A ^ [/ math] на матрицата [math] A [/ math] играе същата роля в теорията на линейните уравнения в затворени полукольца като обратната матрица в класическата линейна алгебра.

Основната роля при решаването на проблеми в теорията на насочените графики и теорията на формалните езици се играе от праволинейни уравнения на формата (3.17), така че по правило ще разглеждаме само тях. Лявото линейно уравнение (3.18) може да се анализира по подобен начин.

Доказахме съществуването на решения на матрични уравнения в матрично полуколеро върху затворено полуколеро. Сега трябва да разработим техника за намиране на техните решения и да я приложим за решаване на системи от формата (3.16).

Ако приемем, че [math] \ xi_j [/ math] е j-тата колона на матрицата [math] X [/ math], [math] \ beta_j [/ math] е j-тата колона на матрицата [math ] B [/ math], уравнение (3.17) може да бъде пренаписано като система от уравнения за неизвестните колони на матрицата [math] X: [/ math]

Всяка система от формата (3.21) е матрична нотация на горната система (3.16). Следователно, най-малкото решение на тази система, както следва от (3.19), е

За да се намери решение на система от формата (3.21), може да се използва методът на последователно елиминиране на неизвестни, подобен на класическия метод на Гаус.

Тъй като системата от уравнения на формата (3.16) има решение, можем да го заместим в системата и да работим с уравненията както с идентичностите.

Помислете за процедурата за решаване на системата от уравнения (3.16). Пишем първото уравнение на системата, както следва:

От първото уравнение на системата изразяваме [math] x_1 [/ math] по отношение на останалите неизвестни, използвайки формула (3.14):

Във формула (3.23) изразът в скоби не съдържа неизвестното [math] x_1 [/ math]. Замествайки (3.23) вместо [math] x_1 [/ math] в останалите уравнения, получаваме система от [math] n-1 [/ math] уравнение, която вече не съдържа [math] x_1: [/ math ]

Довеждайки подобни термини във всяко уравнение на системата, получаваме:

Нека препишем първото уравнение на тази система, както следва:

Имайте предвид, че [math] \ gamma_3 [/ math] не съдържа [math] x_1 [/ math] и [math] x_2 [/ math]. Използвайки релацията (3.14), имаме

където [math] \ alpha_2 = a_a_ ^ a_ + a _ [/ math] не съдържа неизвестни. Използвайки получения израз, изключете [math] x_2 [/ math] от останалите уравнения.

Продължавайки по подобен начин, при i-тата стъпка [math] (1 \ leqslant i \ leqslant n) [/ math] получаваме

където израз [математика] \ alpha_^ [/ math] не съдържа неизвестни, а изразът [math] \ gamma_i [/ ​​math] може да съдържа само неизвестни, започвайки с (i + 1) th, тоест [math] x _, \ ldots, x_n [/ math] .

За [math] i = n [/ math] имаме

Вторият етап на алгоритъма, наречен обратен на метода на Гаус, се състои в последователно намиране на стойността на всички неизвестни [math] x_1, \ ldots, x _ [/ math], започвайки с [math] x _ [/ math]. Замествайки дясната страна (3.28) в израза за [math] x _ [/ math] вместо [math] x_n [/ math], ще намерим [math] x _ [/ math]. След това дефинираме [math] x _ [/ math], като заместваме получените стойности [math] x _ [/ math] и [math] x _ [/ math] в дясната страна на израза (3.27) с [math ] i = n-2 [/ math] и така нататък, докато намерим [math] x_1 [/ math] .

Забележка 3.2. Поставяйки [math] B = E [/ math] в уравнение (3.17), получаваме [math] X = A ^ E = A ^ [/ math]. По този начин, за да се изчисли итерацията на матрицата [math] A [/ math], е достатъчно да се реши матричното уравнение (3.21) за всички [math] j = \ overline [/ math] с [math] \ beta_j [/ math] равна на j- та колона на матрицата за идентичност [math] E [/ math] .

Пример 3.6. Нека илюстрираме горната схема за решаване на система от две линейни уравнения. Ние имаме

От първото уравнение изразяваме [math] x_1: [/ math] - получаваме [math] x_1 = a_ ^ (a_x_2 + b_1) [/ math]. Замествайки този израз във второто уравнение, получаваме

Замествайки този резултат в израза за xi, написан по-горе, намираме крайното решение:

Решението изглежда особено просто в случай на тривиална итерация, т.е. ако при полукопиране итерацията на който и да е елемент е равна на една от полуколерата (както е в полуколките [math] \ mathcal, \ mathcal ^, \ mathcal_A, \ mathcal _ [/ math]). В този случай решението е за система от две уравнения

Пример 3.7. Помислете в полукопирането [math] \ mathcal _ [/ math] (вижте пример 3.3.d) системата от линейни уравнения

Нека решим тази система от уравнения, следвайки общия алгоритъм. От първото уравнение получаваме

Следователно [математика] x_2 = (0, \! 3 + 0, \! 9) x_2 + 0, \! 6 = 0, \! 9x_2 + 0, \! 6 = 0, \! 9 ^ 0, \! 6 = 0, \! 6 \,. [/ Math]. Замествайки [math] x_2 = 0, \! 6 [/ math] в получения израз за [math] x_1 [/ math], откриваме, че

Полусеанси с итерация

Не всяко безкрайно идемпотентно полукопиране е затворено. Въпреки това може да се отбележи, че при решаването на линейни уравнения и системи се изискваше да се изчисли точната горна граница за последователности от специален тип, а именно да се намери итерацията на елементите. Следователно, в допълнение към затворените полуколки, интерес за приложения са така наречените полуколки с итерация.

Под полуколяно с итерация в този контекст имаме предвид идемпотентен полуколерен, който е полуколярен на някакъв затворен полуколерен и, заедно с всеки елемент, съдържа неговата итерация. Най-важният пример за такова полуколко е полуколенето на редовни езици.

Полукоренето [math] \ mathcal = (Q, +, \ cdot, \ bold, \ bold) [/ math] се нарича полукопиране на полуколенето [math] \ mathcal = (R, +, \ cdot, \ bold, \ bold) [/ math], ако множеството [math] Q [/ math] е подмножество на множеството [math] R [/ math], затворено в рамките на операциите на събиране и умножение на полуколенето [math] \ mathcal [/ math], а също така съдържа нула и един от полуколерата [math] \ mathcal [/ math] .

Разглеждането на произволно линейно уравнение в полуколектор с итерация, т.е. уравнение на формата (3.12) или (3.13), получаваме следните резултати. Първо, това уравнение има най-малкото решение, тъй като итерираното полуколене се съдържа в някакво затворено полуколеро като полуколяно. Второ, това най-малко решение отново ще се появи в същия полуколектор, тъй като опората на полуколерта с итерация е затворена по отношение на итерацията. По този начин, опората на полукопирането [math] \ mathcal [/ math] с итерация се затваря при операцията за намиране на най-малката фиксирана точка на която и да е линейна карта [math] ax + b [/ math] (или [math] xa + b [/ math]), където [math] a [/ math] и [math] b [/ math] са елементи на [math] \ mathcal [/ math] .

Не е трудно да се разшири този резултат до произволни матрични уравнения. Следното твърдение може да бъде доказано.

Теорема 3.9. Ако [math] A [/ math] е матрица, всички елементи от която принадлежат към някакво полуколене с итерация, тогава всички елементи от нейната итерация [math] A ^ [/ math] също принадлежат към това полукопиране с итерация.