SENT PETERBURG DAVLAT UNIVERSITETI

Amaliy matematika fakulteti - Boshqarish jarayonlari

A. P. IVANOV

SON USULLAR BO'YICHA SEMINAR

CHIZIQLI ALGEBRAIK TENGLAMALAR TIZIMLARINI YECHISH

Ko'rsatmalar

Sankt-Peterburg

1-BOB. QO'SHIMCHA MA'LUMOT

IN uslubiy qo‘llanma SLAE ni yechish usullari tasnifi va ularni qo'llash algoritmlari berilgan. Usullar boshqa manbalarga murojaat qilmasdan foydalanishga imkon beruvchi shaklda keltirilgan. Tizimning matritsasi yagona emas deb taxmin qilinadi, ya'ni. det A 6= 0.

§1. Vektorlar va matritsalar normalari

Eslatib o'tamiz, x elementlarning Ō chiziqli fazosi Ō fazoning barcha elementlari uchun aniqlangan va quyidagi shartlarni qondiradigan k · kŌ funksiyani o'z ichiga olgan bo'lsa, normallashtirilgan deyiladi:

1. kxk Ō ≥ 0, va kxkŌ = 0 x = 0Ō;

2. klxk Ō = |l| kxkŌ;

3. kx + ykŌ ≤ kxkũ + kykũ .

Kelajakda biz vektorlarni kichik lotin harflari bilan belgilashga rozi bo'lamiz va biz ularni ustun vektorlari deb hisoblaymiz, matritsalarni bosh lotin harflari bilan belgilaymiz va skalyar miqdorlarni yunon harflari bilan belgilaymiz (harflar orqasida butun sonlarning belgilarini saqlab qolamiz. i, j, k, l, m, n) .

Eng ko'p ishlatiladigan vektor normalari quyidagilarni o'z ichiga oladi:

2. kxk2 = u x2 ; t

3. kxk∞ = maxi |xi |.

E'tibor bering, Rn fazodagi barcha normalar ekvivalentdir, ya'ni. kxki va kxkj har qanday ikkita norma bilan bog'langan:

aij kxkj ≤ kxki ≤ bij kxkj,

k k ≤ k k ≤ ˜ k k

a˜ ij x i x j b ij x i,

bundan tashqari, aij , bij , a˜ij , bijlar x ga bogʻliq emas. Bundan tashqari, chekli o'lchovli fazoda har qanday ikkita norma ekvivalentdir.

Matritsalar fazosi tabiiy ravishda kiritilgan songa qo'shish va ko'paytirish amallari bilan norma tushunchasini ko'p jihatdan kiritish mumkin bo'lgan chiziqli fazoni tashkil qiladi. Biroq, bo'ysunuvchi me'yorlar deb ataladigan narsalar ko'pincha ko'rib chiqiladi, ya'ni. munosabatlar tomonidan vektor normalari bilan bog'liq normalar:

Matritsalarning subordinatsiya normalarini vektorlarning tegishli normalari bilan bir xil indekslar bilan belgilab, shuni aniqlashimiz mumkinki,

Bu yerda li (AT A) AT A matritsasining xos qiymatini bildiradi, bu yerda AT – A ga ko‘chirilgan matritsa. Yuqorida qayd etilgan me’yorning uchta asosiy xususiyatidan tashqari, bu yerda yana ikkitasini qayd etamiz:

kABk ≤ kAk kBk,

kAxk ≤ kAk kxk,

bundan tashqari, oxirgi tengsizlikda matritsa normasi mos keladigan vektor normasiga bo'ysunadi. Keling, faqat vektorlar normalariga bo'ysunadigan matritsalar normalaridan keyingi narsada foydalanishga rozi bo'laylik. E'tibor bering, bunday normalar uchun tenglik amal qiladi: agar E identifikatsiya matritsasi bo'lsa, u holda kEk = 1, .

§2. Diagonal ustunlikka ega matritsalar

Ta'rif 2.1. (aij )n i,j=1 elementlarga ega boʻlgan A matritsa, agar tengsizliklar boʻlsa, diagonal dominantlik (qiymatlari d) boʻlgan matritsa deyiladi.

|ai | − |aij| ≥ d > 0, i = 1, n .

§3. Ijobiy aniq matritsalar

Ta'rif 3.1. Simmetrik matritsa A chaqiriladi

ijobiy aniqlangan, agar bu matritsaga ega xT Ax kvadratik shakli har qanday vektor x 6= 0 uchun faqat ijobiy qiymatlarni qabul qilsa.

Matritsaning ijobiy aniqligi mezoni uning xos qiymatlarining ijobiyligi yoki asosiy kichiklarining ijobiyligi bo'lishi mumkin.

§4. SLAE shart raqami

Har qanday muammoni hal qilishda, ma'lumki, uch xil xatolar mavjud: halokatli xato, uslubiy xato va yaxlitlash xatosi. Keling, yaxlitlash xatosini e'tiborsiz qoldirib, uslubiy xatoning yo'qligini hisobga olgan holda, dastlabki ma'lumotlarning halokatli xatosining SLAE ni hal qilishga ta'sirini ko'rib chiqaylik.

matritsasi A aniq ma'lum va o'ng tomoni b o'chirilmaydigan xato b b o'z ichiga oladi.

Keyin yechimning nisbiy xatosi uchun kdxk/kxk

bu yerda n(A) = kAkkA−1k.

n(A) soni sistemaning shart raqami (4.1) (yoki A matritsasi) deb ataladi. Ma'lum bo'lishicha, har qanday A matritsa uchun har doim n(A) ≥ 1 bo'ladi. Shart raqamining qiymati matritsa normasini tanlashga bog'liq bo'lganligi sababli, aniq normani tanlashda biz mos ravishda n(A) indeksini olamiz: n1 ( A), n2 (A) yoki n ∞(A).

n(A) 1 holatda sistema (4.1) yoki A matritsa yomon shartli deyiladi. Bu holda, smetadan quyidagicha

(4.2) bo'lsa, (4.1) tizimning yechimidagi xatolik qabul qilib bo'lmaydigan darajada katta bo'lishi mumkin. Xatoning maqbulligi yoki qabul qilinmasligi tushunchasi muammoni shakllantirish bilan belgilanadi.

Diagonal ustunlikka ega matritsa uchun uning shart raqamining yuqori bahosini olish oson. Ro'y beradi

4.1 teorema. A diagonali dominantligi d > 0 bo‘lgan matritsa bo‘lsin. U holda u yagona bo‘lmagan va n∞ (A) ≤ kAk∞ /d bo‘ladi.

§5. Noto'g'ri tizimga misol.

SLAE (4.1) ni ko'rib chiqing, unda

Bu sistema x = (0, 0, . . ., 0, 1)T ning yagona yechimiga ega. Tizimning o'ng tomonida db = (0, 0, . . , 0, e), e > 0 xatosi bo'lsin.

dxn = e, dxn−1 = e, dxn−2 = 2 e, dxn−k = 2 k−1 e, . . . , dx1 = 2n−2e.

Demak,

n∞ (A) ≥ kdxk ∞ : kbk ∞ = 2n−2 . kxk ∞ kbk ∞

kAk∞ = n ekan, u holda kA−1 k∞ ≥ n−1 2 n−2 , garchi det(A−1 ) = (det A)−1 = 1. Masalan, n = 102. U holda n( A ) ≥ 2100 > 1030. Bundan tashqari, e = 10−15 bo'lsa ham, biz kdxk∞ > 1015 ni olamiz. Va bu emas

Ta'rif.

Agar matritsaning elementlari bo'lsa, qator diagonali ustunlikka ega bo'lgan tizimni sistema deb ataymiztengsizliklarni qanoatlantiring:

,

Tengsizliklar matritsaning har bir satrida ekanligini bildiradi diagonal element ta'kidlangan: uning moduli bir xil qatorning barcha boshqa elementlarining modullari yig'indisidan kattaroqdir.

Teorema

Diagonal ustunlikka ega bo'lgan tizim har doim echilishi mumkin va bundan tashqari, noyobdir.

Tegishli bir hil tizimni ko'rib chiqing:

,

Faraz qilaylik, uning ahamiyatsiz yechimi bor , Ushbu yechimning eng katta modulga ega bo'lgan komponenti indeksga mos kelsin
, ya'ni.

,
,
.

Keling, yozamiz shakldagi sistemaning th tenglamasi

va bu tenglikning ikkala tomonining modulini oling. Natijada biz quyidagilarni olamiz:

.

Tengsizlikni omil bilan kamaytirish
, bu esa nolga teng emas, diagonal ustunlikni ifodalovchi tengsizlik bilan ziddiyatga kelamiz. Olingan qarama-qarshilik bizga uchta bayonotni izchil bayon qilish imkonini beradi:

Ularning oxirgisi teoremaning isboti to'liq ekanligini bildiradi.

1. Tridiagonal matritsali tizimlar. Tozalash usuli.

Ko'pgina muammolarni hal qilishda quyidagi shakldagi chiziqli tenglamalar tizimlari bilan shug'ullanish kerak:

,
,

,
,

bu erda koeffitsientlar
, o'ng tomonlar
raqamlar bilan birga ma'lum Va . Qo'shimcha munosabatlar ko'pincha tizim uchun chegara shartlari deb ataladi. Ko'p hollarda ular yanada murakkab ko'rinishga ega bo'lishi mumkin. Masalan:

;
,

Qayerda
raqamlar beriladi. Biroq, taqdimotni murakkablashtirmaslik uchun biz qo'shimcha shartlarning eng oddiy shakli bilan cheklanamiz.

Qadriyatlar mavjudligidan foydalanib Va berilgan bo'lsa, biz tizimni quyidagi shaklda qayta yozamiz:

Ushbu tizimning matritsasi tridiagonal tuzilishga ega:

Bu tozalash usuli deb ataladigan maxsus usul tufayli tizimning yechimini sezilarli darajada osonlashtiradi.

Usul kerakli noma'lumlar degan taxminga asoslanadi Va
takrorlanish munosabati bilan bog'liq

,
.

Bu erda miqdorlar
,
, supurish koeffitsientlari deb ataladi, masalaning shartlaridan kelib chiqqan holda aniqlanishi kerak, . Aslida, bunday tartib noma'lumlarning bevosita ta'rifini almashtirishni anglatadi keyinchalik miqdorlarni hisoblash bilan tozalash koeffitsientlarini aniqlash vazifasi .

Ta'riflangan dasturni amalga oshirish uchun biz munosabat yordamida ifodalaymiz
orqali
:

va almashtiring
Va , orqali ifodalangan
, asl tenglamalarga. Natijada biz quyidagilarni olamiz:

.

Oxirgi munosabatlar, albatta, qoniqtiriladi va bundan tashqari, yechimdan qat'i nazar, agar talab etilsa.
tenglik yuzaga keldi:

Bu yerdan tozalash koeffitsientlari uchun rekursiv munosabatlarga amal qiling:

,
,
.

Chap chegara holati
va nisbat
qo'ysak, izchil bo'ladi

.

Supurish koeffitsientlarining boshqa qiymatlari
Va
biz qaysidan topamiz va supurish koeffitsientlarini hisoblash bosqichini yakunlaymiz.

.

Bu erdan qolgan noma'lum narsalarni topishingiz mumkin
rekursiv formula yordamida orqaga supurish jarayonida.

Gauss usuli yordamida umumiy tizimni yechish uchun zarur bo'lgan operatsiyalar soni ortib boradi mutanosib ravishda . Supurish usuli ikki tsiklga qisqartiriladi: birinchi navbatda, formulalar yordamida tozalash koeffitsientlari hisoblanadi, so'ngra ulardan foydalanib, takroriy formulalar yordamida tizim yechimining tarkibiy qismlari topiladi. . Bu shuni anglatadiki, tizim hajmi kattalashgani sayin arifmetik amallar soni mutanosib ravishda oshadi. , lekin emas . Shunday qilib, uning mumkin bo'lgan qo'llanilishi doirasida tozalash usuli sezilarli darajada tejamkor. Bunga uning dasturiy ta'minotini kompyuterda amalga oshirishning alohida soddaligini qo'shish kerak.

Tridiagonal matritsa bilan SLAEga olib keladigan ko'plab amaliy masalalarda uning koeffitsientlari tengsizliklarni qondiradi:

,

diagonal ustunlik xususiyatini ifodalovchi. Xususan, biz uchinchi va beshinchi boblarda bunday tizimlar bilan tanishamiz.

Oldingi bo'lim teoremasiga ko'ra, bunday tizimlarning yechimi doimo mavjud va yagonadir. Ular, shuningdek, supurish usuli yordamida yechimni haqiqiy hisoblash uchun muhim bo'lgan bayonotga ega.

Lemma

Agar tridiagonal matritsali tizim uchun diagonal dominantlik sharti bajarilsa, supurish koeffitsientlari tengsizliklarni qondiradi:

.

Biz isbotni induksiya yo'li bilan bajaramiz. Ga binoan
, Men yeyman
lemmaning tasdiqlanishi haqiqatdir. Keling, bu to'g'ri deb faraz qilaylik va ko'rib chiqing
:

.

Shunday qilib, induksiya dan Kimga
oqlangan, bu esa lemmaning isbotini tugallaydi.

Supurish koeffitsientlari uchun tengsizlik yugurishni barqaror qiladi. Haqiqatan ham, yechim komponenti deylik yaxlitlash protsedurasi natijasida ba'zi xato bilan hisoblanadi. Keyin keyingi komponentni hisoblashda
rekursiv formulaga ko'ra, bu xato, tengsizlik tufayli ko'paymaydi.

MATRIXALARNING NODEGENERLIGI VA DIAGONAL DOMINANT XUSUSIYASI1

L. Tsvetkovich, V. Kostic va L.A. Crookier

Tsvetkovich Liliana - Novi Sad universiteti, Fanlar fakulteti, matematika va informatika kafedrasi professori, Serbiya, Obradovitsa 4, Novi Sad, Serbiya, 21000, e-mail: [elektron pochta himoyalangan]

Kostic Vladimir - Novi Sad universiteti, Fanlar fakulteti, matematika va informatika kafedrasi dotsenti, Serbiya, Obradovitsa 4, 21000, Novi Sad, Serbiya, elektron pochta: [elektron pochta himoyalangan]

Krukier Lev Abramovich - fizika-matematika fanlari doktori, professor, yuqori unumli hisoblash va axborot-kommunikatsiya texnologiyalari kafedrasi mudiri, Janubiy Rossiya mintaqaviy axborotlashtirish markazi direktori federal universitet, Stachki prospekti, 200/1, uy. 2, Rostov-Don, 344090, elektron pochta: [elektron pochta himoyalangan] ru.

Tsvetkovich Ljiljana - Novi Sad universiteti, Fanlar fakulteti, matematika va informatika kafedrasi professori, Serbiya, D. Obradovitsa 4, Novi Sad, Serbiya, 21000, e-mail: [elektron pochta himoyalangan]

Kostic Vladimir - Novi Sad universiteti, Fanlar fakulteti, matematika va informatika kafedrasi assistenti, Serbiya, D. Obradovitsa 4, Novi Sad, Serbiya, 21000, e-mail: [elektron pochta himoyalangan]

Krukier Lev Abramovich - fizika-matematika fanlari doktori, professor, yuqori unumli hisoblash va axborot-kommunikatsiya texnologiyalari kafedrasi mudiri, Janubiy Federal universiteti kompyuter markazi direktori, Stachki prospekti, 200/1, bild. 2, Rostov-Don, Rossiya, 344090, elektron pochta: [elektron pochta himoyalangan] ru.

Matritsadagi diagonal ustunlik oddiy holat, uning degeneratsiyasini ta'minlash. Diagonal dominantlik tushunchasini umumlashtiruvchi matritsa xossalari har doim yuqori talabga ega. Ular diagonal dominantlik tipidagi shartlar sifatida ko'rib chiqiladi va matritsalarning pastki sinflarini (masalan, H-matritsalar) aniqlashga yordam beradi, ular bu sharoitlarda degenerativ bo'lmagan. Ushbu maqolada biz diagonal ustunlikning afzalliklarini saqlaydigan, lekin H-matritsalar sinfidan tashqarida qoladigan yagona bo'lmagan matritsalarning yangi sinflarini quramiz. Bu xususiyatlar ayniqsa qulaydir, chunki ko'plab ilovalar ushbu sinfdagi matritsalarga olib keladi va H-matritsalari bo'lmagan matritsalarning degenerativ bo'lmasligi nazariyasi endi kengaytirilishi mumkin.

Kalit so'zlar: diagonal ustunlik, degeneratsiyaga uchramaslik, masshtablash.

Matritsalarning yagona bo'lmaganligini ta'minlaydigan oddiy shartlar har doim juda mamnuniyat bilan qabul qilingan bo'lsa-da, ularning ko'pchiligi diagonal dominantlikning bir turi sifatida ko'rib chiqilishi mumkin bo'lgan yaxshi ma'lum bo'lgan H-matritsalarining kichik sinflarini hosil qiladi. Ushbu maqolada biz diagonal ustunlikning foydaliligini saqlaydigan, lekin H-matritsalar sinfi bilan umumiy munosabatda bo'lgan yagona bo'lmagan matritsalarning yangi sinflarini quramiz. Bu xususiyat ayniqsa qulaydir, chunki H-matritsa nazariyasidan kelib chiqadigan ko'plab ilovalar endi kengaytirilishi mumkin.

Kalit so'zlar: diagonal ustunlik, nosingularlik, masshtablash texnikasi.

Matematik fizikaning chegaraviy masalalarini sonli yechish odatda asl masalani chiziqli algebraik tenglamalar sistemasi yechimiga qisqartiradi. Yechim algoritmini tanlashda biz asl matritsaning yagona emasligini bilishimiz kerakmi? Bundan tashqari, matritsaning degenerativ emasligi masalasi, masalan, iterativ usullarning yaqinlashuvi nazariyasida, xususiy qiymatlarni lokalizatsiya qilishda, determinantlarni, Apron ildizlarini, spektral radiusni, singulyar qiymatlarni baholashda dolzarbdir. matritsa va boshqalar.

E'tibor bering, matritsaning degeneratsiyasini ta'minlaydigan eng oddiy, ammo juda foydali shartlardan biri bu qattiq diagonal ustunlikning taniqli xususiyati (va ularga havolalar).

Teorema 1. A = e Cnxn matritsasi shunday berilgan bo'lsin

s > r (a):= S k l, (1)

hamma uchun i e N:= (1,2,...n).

U holda A matritsasi degenerativ emas.

(1) xossaga ega matritsalar qattiq diagonal ustunlikka ega matritsalar deyiladi

(8BB matritsalari). Ularning tabiiy umumlashtirilishi umumiy diagonal ustunlik (GBD) bo'lgan matritsalar sinfi bo'lib, quyidagicha aniqlanadi:

Ta'rif 1. A = [a^] e Cxn matritsasi sBB matritsasi deyiladi, agar AW 8BB matritsa bo'ladigan yagona bo'lmagan diagonal W matritsa mavjud bo'lsa.

Biz matritsa uchun bir nechta ta'riflarni kiritamiz

A \u003d [ay] e Spxp.

Ta'rif 2

(A) = e Cn

A matritsaning taqqoslash matritsasi deyiladi.

Ta'rif 3. Matritsa A = e C

\üj > 0, i = j

agar M-matritsadir

aj< 0, i * j,

teskari mat-

matritsa A">0, ya'ni uning barcha elementlari ijobiydir.

Shubhasiz, wBB sinfidagi matritsalar ham yagona bo'lmagan matritsalar va bo'lishi mumkin

1Bu ish qisman Serbiya Ta'lim va fan vazirligi tomonidan qo'llab-quvvatlandi, grant 174019 va Voyvodina Fan va texnologik taraqqiyot vazirligi, grantlar 2675 va 01850.

adabiyotlarda degenerativ bo'lmagan H-matritsalar nomi bilan topilgan. Ularni quyidagi zarur va yetarli shartlar yordamida aniqlash mumkin:

Teorema 2. A \u003d [ay ]e xi matritsasi

matritsa, agar uning taqqoslash matritsasi degenerativ bo'lmagan M-matritsa bo'lsa.

Hozirgi vaqtda degenerativ bo'lmagan H-matritsalarining ko'plab kichik sinflari allaqachon o'rganilgan, ammo ularning barchasi qat'iy diagonal dominantlik xususiyatini umumlashtirish nuqtai nazaridan ko'rib chiqiladi (shuningdek, havolalarga qarang).

Ushbu maqolada biz SBB sinfini boshqacha tarzda umumlashtirish orqali H-matritsalar sinfidan tashqariga chiqish imkoniyatini ko'rib chiqamiz. Asosiy g'oya masshtablash usulidan foydalanishni davom ettirishdir, lekin diagonal bo'lmagan matritsalar bilan.

A \u003d [ay ] e spxn matritsasi va indeksni ko'rib chiqing

Biz matritsa bilan tanishamiz

r (A):= £ a R (A):= £

ßk (A) := £ va yk (A) := aü - ^

bk Abk matritsasining elementlari quyidagi shaklga ega ekanligini tekshirish oson:

ßk (A), Y k (A), akj,

i=j=k, i=j*k,

i = k, j * k, i * k, j = k,

A inöaeüiüö neo^äyö.

Agar 1-teoremani yuqorida bayon qilingan bk Abk1 matritsaga va uning transpozitsiyasiga qo‘llasak, ikkita asosiy teoremaga erishamiz.

Teorema 3. Har qanday matritsa berilgan bo'lsin

A \u003d [ay ] e spxn diagonali nolga teng bo'lmagan elementlarga ega. Agar > Rk (A) va har bir i e N \ (k) bo'ladigan k e N mavjud bo'lsa,

u holda A matritsasi degenerativ emas.

Teorema 4. Har qanday matritsa berilgan bo'lsin

A \u003d [ay ] e spxn diagonali nolga teng bo'lmagan elementlarga ega. Agar > Jk (A) va har bir i e N \ (k) bo'lgan k e N mavjud bo'lsa,

U holda A matritsasi degenerativ emas. O'rtasidagi munosabatlar haqida tabiiy savol tug'iladi

oldingi ikkita teoremadagi matritsalar: L^ - BOO -matritsalar ( formula bilan aniqlanadi(5)) va

bk - BOO-matritsalar ((6) formula bilan aniqlanadi) va H-matritsalar sinfi. Quyidagi oddiy misol buni aniq ko'rsatib turibdi.

Misol. Quyidagi 4 ta matritsani ko'rib chiqing:

va dastlabki A ga o'xshash bk Abk, k e N matritsani ko'rib chiqaylik. Bu matritsa SDD-matritsa xossasiga (satr yoki ustunlar bo'yicha) ega bo'lish shartlarini topaylik.

Maqola davomida r,k eN:= (1,2,.../?) uchun quyidagi belgidan foydalanamiz:

2 2 1 1 3 -1 1 1 1

" 2 11 -1 2 1 1 2 3

2 1 1 1 2 -1 1 1 5

Degeneratsiyaga oid teoremalar

Ularning barchasi degenerativ emas:

A1 har qanday k = (1,2,3) uchun bk - BOO emasligiga qaramay, b - BOO. Bundan tashqari, u H-matritsa emas, chunki (A^1 manfiy emas;

A2, simmetriya tufayli, bir vaqtning o'zida LH - BOO va L<2 - БОО, так же как ЬЯ - БОО и

b<3 - БОО, но не является Н-матрицей, так как (А2) вырожденная;

A3 b9 - BOO, lekin hech biri emas

Lr SDD (k = (1,2,3) uchun), na H-matritsa, chunki (A3 ^ ham degenerativ;

A4 H-matritsadir, chunki (A^ nosingular va ^A4) 1 > 0, garchi u har qanday k = (1,2,3) uchun LR - SDD ham, Lk - SDD ham emas.

Rasm o'rtasidagi umumiy munosabatni ko'rsatadi

Lr - SDD , Lk - SDD va H-matritsalar oldingi misoldagi matritsalar bilan birga.

lR - SDD, lC - SDD va o'rtasidagi aloqa

jahannam min(|au - r (A)|) "

Tengsizlikdan boshlash

va bu natijani bk ab ^ matritsasiga qo'llasak, hosil bo'lamiz

Teorema 5. Diagonal elementlari nolga teng bo'lmagan ixtiyoriy A = [a--] e Cxn matritsasi berilsin.

politsiya. Agar A sinfga tegishli bo'lsa - BOO, keyin

1 + maksimal^ i*k \acc\

H-matritsalar

Shunisi qiziqki, bizda bor bo'lsa-da

LC AL^1 matritsasini koʻchirish natijasida olingan matritsaga 1-teoremani qoʻllash orqali LC BOO-matritsalari sinfi, bu klass Am matritsaga 2-teoremani qoʻllash natijasida olingan sinfga toʻgʻri kelmaydi.

Biz ta'riflarni kiritamiz.

Ta'rif 4. Agar AT ( bk -boo ) bo'lsa, A matritsasi ( bk -boo satrlar bo'yicha) deyiladi.

Ta'rif 5. Agar AT ( bsk -boo ) bo'lsa, A matritsasi ( bsk -boo satrlar bo'yicha) deyiladi.

Misollar shuni ko'rsatadiki, W - BOO sinflari,

bc-boo, (qator bo'yicha bk-boo) va (b^-boo) bir-biriga bog'langan. Shunday qilib, biz H-matritsalar sinfini to'rt xil usulda kengaytirdik.

Yangi teoremalarni qo'llash

Keling, teskari matritsaning C-normasini baholashda yangi natijalarning foydaliligini ko'rsatamiz.

Qattiq diagonal ustunlikka ega ixtiyoriy A matritsa uchun mashhur Varah teoremasi (Varah) taxminni beradi.

min[|pf(A)| - mk (A), min(|yk (A)| - qk(A) - |af (A)|)]" i i (Ff ​​ii ii)

Xuddi shunday, ustunlar bo'yicha Lk - SDD matritsalari uchun quyidagi natijani olamiz.

Teorema 6. Diagonal elementlari nolga teng bo'lmagan ixtiyoriy A = e xi matritsa berilsin. Agar A ustunlar bo'yicha bk -SDD sinfiga tegishli bo'lsa, u holda

Ik-lll<_ie#|akk|_

" "mln[|pf(A)| - Rf (AT), million(|uk (A)|- qk (AT)- |aft |)]"

Bu natijaning ahamiyati shundaki, yagona bo'lmagan H-matritsalarning ko'plab kichik sinflari uchun ushbu turdagi cheklovlar mavjud, ammo H-matritsalari bo'lmagan yagona bo'lmagan matritsalar uchun bu ahamiyatsiz muammodir. Shuning uchun, oldingi teoremadagi kabi, bunday turdagi cheklovlar katta talabga ega.

Adabiyot

Levy L. Sur le possibilité du l "equlibre electrique C. R. Acad. Paris, 1881. Vol. 93. P. 706-708.

Horn R.A., Jonson C.R. matritsa tahlili. Kembrij, 1994. Varga R.S. Gersgorin va uning doiralari // Hisoblash matematikasidagi Springer seriyasi. 2004 jild. 36.226 b. Berman A., Plemons R.J. Matematik fanlarda manfiy bo'lmagan matritsalar. Amaliy matematikada SIAM seriyali klassiklar. 1994 jild. 9. 340 rubl

Tsvetkovich Lj. H-matritsa nazariyasi va boshqalar. Xususiy qiymatning lokalizatsiyasi // Raqam. Algor. 2006 jild. 42. 229-245-betlar. Cvetkovich Lj., Kostic V., Kovacevic M., Szulc T. H-matritsalari va ularning Schur to'ldiruvchisi bo'yicha keyingi natijalar // Appl. Matematika. Hisoblash. 1982. B. 506-510.

Varah J.M. Matritsaning eng kichik qiymati uchun pastki chegara // Lineer Algebra Appl. 1975 jild. 11. B. 3-5.

Muharrir tomonidan qabul qilingan

Ta'rif.

Agar matritsaning elementlari bo'lsa, qator diagonali ustunlikka ega bo'lgan tizimni sistema deb ataymiztengsizliklarni qanoatlantiring:

,

Tengsizliklar matritsaning har bir satrida ekanligini bildiradi diagonal element ta'kidlangan: uning moduli bir xil qatorning barcha boshqa elementlarining modullari yig'indisidan kattaroqdir.

Teorema

Diagonal ustunlikka ega bo'lgan tizim har doim echilishi mumkin va bundan tashqari, noyobdir.

Tegishli bir hil tizimni ko'rib chiqing:

,

Faraz qilaylik, uning ahamiyatsiz yechimi bor , Ushbu yechimning eng katta modulga ega bo'lgan komponenti indeksga mos kelsin
, ya'ni.

,
,
.

Keling, yozamiz shakldagi sistemaning th tenglamasi

va bu tenglikning ikkala tomonining modulini oling. Natijada biz quyidagilarni olamiz:

.

Tengsizlikni omil bilan kamaytirish
, bu esa nolga teng emas, diagonal ustunlikni ifodalovchi tengsizlik bilan ziddiyatga kelamiz. Olingan qarama-qarshilik bizga uchta bayonotni izchil bayon qilish imkonini beradi:

Ularning oxirgisi teoremaning isboti to'liq ekanligini bildiradi.

1. Tridiagonal matritsali tizimlar. Tozalash usuli.

Ko'pgina muammolarni hal qilishda quyidagi shakldagi chiziqli tenglamalar tizimlari bilan shug'ullanish kerak:

,
,

,
,

bu erda koeffitsientlar
, o'ng tomonlar
raqamlar bilan birga ma'lum Va . Qo'shimcha munosabatlar ko'pincha tizim uchun chegara shartlari deb ataladi. Ko'p hollarda ular yanada murakkab ko'rinishga ega bo'lishi mumkin. Masalan:

;
,

Qayerda
raqamlar beriladi. Biroq, taqdimotni murakkablashtirmaslik uchun biz qo'shimcha shartlarning eng oddiy shakli bilan cheklanamiz.

Qadriyatlar mavjudligidan foydalanib Va berilgan bo'lsa, biz tizimni quyidagi shaklda qayta yozamiz:

Ushbu tizimning matritsasi tridiagonal tuzilishga ega:

Bu tozalash usuli deb ataladigan maxsus usul tufayli tizimning yechimini sezilarli darajada osonlashtiradi.

Usul kerakli noma'lumlar degan taxminga asoslanadi Va
takrorlanish munosabati bilan bog'liq

,
.

Bu erda miqdorlar
,
, supurish koeffitsientlari deb ataladi, masalaning shartlaridan kelib chiqqan holda aniqlanishi kerak, . Aslida, bunday tartib noma'lumlarning bevosita ta'rifini almashtirishni anglatadi keyinchalik miqdorlarni hisoblash bilan tozalash koeffitsientlarini aniqlash vazifasi .

Ta'riflangan dasturni amalga oshirish uchun biz munosabat yordamida ifodalaymiz
orqali
:

va almashtiring
Va , orqali ifodalangan
, asl tenglamalarga. Natijada biz quyidagilarni olamiz:

.

Oxirgi munosabatlar, albatta, qoniqtiriladi va bundan tashqari, yechimdan qat'i nazar, agar talab etilsa.
tenglik yuzaga keldi:

Bu yerdan tozalash koeffitsientlari uchun rekursiv munosabatlarga amal qiling:

,
,
.

Chap chegara holati
va nisbat
qo'ysak, izchil bo'ladi

.

Supurish koeffitsientlarining boshqa qiymatlari
Va
biz qaysidan topamiz va supurish koeffitsientlarini hisoblash bosqichini yakunlaymiz.

.

Bu erdan qolgan noma'lum narsalarni topishingiz mumkin
rekursiv formula yordamida orqaga supurish jarayonida.

Gauss usuli yordamida umumiy tizimni yechish uchun zarur bo'lgan operatsiyalar soni ortib boradi mutanosib ravishda . Supurish usuli ikki tsiklga qisqartiriladi: birinchi navbatda, formulalar yordamida tozalash koeffitsientlari hisoblanadi, so'ngra ulardan foydalanib, takroriy formulalar yordamida tizim yechimining tarkibiy qismlari topiladi. . Bu shuni anglatadiki, tizim hajmi kattalashgani sayin arifmetik amallar soni mutanosib ravishda oshadi. , lekin emas . Shunday qilib, uning mumkin bo'lgan qo'llanilishi doirasida tozalash usuli sezilarli darajada tejamkor. Bunga uning dasturiy ta'minotini kompyuterda amalga oshirishning alohida soddaligini qo'shish kerak.

Tridiagonal matritsa bilan SLAEga olib keladigan ko'plab amaliy masalalarda uning koeffitsientlari tengsizliklarni qondiradi:

,

diagonal ustunlik xususiyatini ifodalovchi. Xususan, biz uchinchi va beshinchi boblarda bunday tizimlar bilan tanishamiz.

Oldingi bo'lim teoremasiga ko'ra, bunday tizimlarning yechimi doimo mavjud va yagonadir. Ular, shuningdek, supurish usuli yordamida yechimni haqiqiy hisoblash uchun muhim bo'lgan bayonotga ega.

Lemma

Agar tridiagonal matritsali tizim uchun diagonal dominantlik sharti bajarilsa, supurish koeffitsientlari tengsizliklarni qondiradi:

.

Biz isbotni induksiya yo'li bilan bajaramiz. Ga binoan
, Men yeyman
lemmaning tasdiqlanishi haqiqatdir. Keling, bu to'g'ri deb faraz qilaylik va ko'rib chiqing
:

.

Shunday qilib, induksiya dan Kimga
oqlangan, bu esa lemmaning isbotini tugallaydi.

Supurish koeffitsientlari uchun tengsizlik yugurishni barqaror qiladi. Haqiqatan ham, yechim komponenti deylik yaxlitlash protsedurasi natijasida ba'zi xato bilan hisoblanadi. Keyin keyingi komponentni hisoblashda
rekursiv formulaga ko'ra, bu xato, tengsizlik tufayli ko'paymaydi.

$|a\_(ii)|\; \backslash geqslant\; \backslash sum\_(j\; \backslash neq\; i)\; |a\_(ij)|,\backslash qquad\; i\; =\; 1,\; \backslash dots,\; n,$

va kamida bitta tengsizlik qat'iydir. Agar barcha tengsizliklar qat'iy bo'lsa, matritsa shunday deyiladi $A\_(nn)$ ega qattiq diagonal ustunlik.

Ilovalarda diagonal ustunlikka ega matritsalar ko'pincha paydo bo'ladi. Ularning asosiy afzalligi shundaki, bunday matritsa bilan SLAE ni yechishning iterativ usullari (oddiy iteratsiya usuli, Zaydel usuli) mavjud bo'lgan va har qanday o'ng tomon uchun noyob bo'lgan aniq yechimga yaqinlashadi.

Xususiyatlari

• Qattiq diagonal ustunlikka ega matritsa degenerativ emas.

Shuningdek qarang

"Diagonal ustunlik" maqolasiga sharh yozing

Diagonal ustunlikni tavsiflovchi parcha