از ویکیپدیا، دانشنامه آزاد

در ریاضیات ، قضیه دایره گرشگورین ممکن است برای محدود کردن طیف یک ماتریس مربع استفاده شود . این نخستین بار توسط سمیون آرونوویچ گرشگورین ، ریاضیدان اتحاد جماهیر شوروی در سال 1931 منتشر شد. نام گرشгоورین به طرق مختلف ترجمه شده است ، از جمله Geršgorin ، Gerschgorin ، Gershgorin ، Hershhorn و Hirschhorn.

 

فهرست

بیانیه و اثبات [ ویرایش ]

اجازه دهیدآیک مجتمع n \ n n ماتریس ، با ورودی من \ در \ {1 ، \ نقطه ، n \ اجازه دهید R_ {i} = \ sum _ {{j \ neq {i}}} \ left | a _ {{ij}} \ Right |مجموعه ای از مقادیر مطلق ورودی های غیر مورب درمن-پرت كردن. اجازه دهید\ displaystyle D (a_ {ii} ، R_ {i}) \ subeteq \ mathbb {C}یک دیسک بسته محور باشدa_ {ii} با شعاع R_ {i. چنین دیسک را دیسک گرشورورین می نامند .

قضیه : هر ارزش ویژه ای ازآ در حداقل یکی از دیسک های گرشورورین قرار دارد.display \ displaystyle D (a_ {ii} ، R_ {i}).

اثبات : بگذارید\ لامبدا  یک مقدمه مهم باشد آ. یک eigenveector مربوطه را انتخاب کنید\ displaystyle x = (x_ {j}) به طوری که یک جزء x_ {من برابر است با 1 و بقیه از ارزش مطلق کمتر یا مساوی برخوردار هستند 1: x_ {i} = 1 و\ displaystyle | x_ {j} | \ leq 1 برای \ displaystyle j \ neq i}. همیشه چنین مواردی وجود داردایکس، که می توان با تقسیم هر ماده خاص برقی با مؤلفه آن با بزرگترین مدول بدست آمد. از آنجا کهAx \ displaystyle Ax = \ lambda x، به خصوص

\ displaystyle \ sum _ {j} a_ {ij} x_ {j} = \ lambda x_ {i} = \ lambda.

بنابراین ، تقسیم مبلغ و یک بار دیگر آن را در نظر می گیریم x_ {i} = 1، ما گرفتیم

\ displaystyle \ sum _ {j \ neq i} a_ {ij} x_ {j} + a_ {ii} = \ lambda.

بنابراین ، با استفاده از نابرابری مثلث ،

\ displaystyle | \ lambda -a_ {ii} | = \ left | \ sum _ {j \ neq i} a_ {ij} x_ {j} \ Right | \ leq \ sum _ {j \ neq i} | a_ ij} || x_ {j} | \ leq \ sum _ {j \ neq i} | a_ {ij} | = R_ {i}.

نتیجه گیری : مقدمات ویژه A نیز باید در دیسکهای Gershgorin C j مطابق با ستونهای A قرار داشته باشد.

اثبات : قضیه را در A T اعمال کنید .

مثال برای یک ماتریس مورب ، دیسکهای گرشورورین همزمان با طیف هستند. برعکس ، اگر دیسکهای گرشورورین همزمان با طیف باشند ، ماتریس مورب است.

بحث [ ویرایش ]

یک راه برای تفسیر این قضیه این است که اگر ورودی های غیر مورب یک ماتریس مربع بر روی اعداد پیچیده دارای هنجارهای کوچکی باشند ، مقادیر ویژه ماتریس نمی توانند "به دور" از ورودی های مورب ماتریس باشند. بنابراین ، با کاهش هنجارهای ورودی های خارج از مورب می توان سعی کرد مقادیر ویژه ای از ماتریس تقریبی داشته باشد. البته ، ورودی های مورب ممکن است در روند به حداقل رساندن ورودی های خارج از مورب تغییر کند.

این قضیه ادعا نمی کند که برای هر مقادیر ویژه یک دیسک وجود دارد. اگر هر چیزی، دیسک های نه به مطابقت محور در\ mathbb {C} ^ {n، و هر یک دقیقاً محدود به موارد ویژه ای هستند که مناطق ویژه آنها نزدیک به یک محور خاص است. در ماتریس

\ displaystyle \ fill {pmatrix 3 & 2 & 2 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \ end {pmatrix}} {\ fill pmatrix} a & 0 & 0 \\ 0 & b & 0 \\ 0 & 0 & c \ end {pmatrix}} {\ \ begin p&rix 1 & 1 & 0 \\ 1 & 0 & 1 \ end {pmatrix}} ^ {- 1} = {\ fill pmatrix -3a + 2b + 2c & 6a-2b-4c & 6a-4b-2c \\ ba & a + (ab) & 2 (ab) \\ ca & 2 ( AC) & a + (ac) \ end {pmatrix}}}

- که با ساخت و ساز دارای مقدمات ویژه ای است آ، بو ج با مجرای نوری {\ نمایش نمایشگر \ چپ ({\ شروع {smallmatrix} 3 \\ 1 \\ 1 \ end {smallmatrix}} \ سمت راست)، {\ نمایش نمایشگر \ چپ ({\ شروع {smallmatrix 2 \\ 1 \\ 0 \ end {smallmatrix}} \ سمت راست)}و {\ displaystyle \ سمت چپ ({\ شروع {smallmatrix} 2 \\ 0 \\ 1 \ end {smallmatrix}} \ Right)} - به راحتی می توان فهمید که دیسک ردیف 2 را در بر می گیرد آ و ب در حالی که دیسک ردیف 3 را پوشش می دهد آ و ج. این با این حال فقط یک اتفاق خوشحال است. اگر از طریق مراحل اثبات کار کنید متوجه می شوید که در هر eigenveector اولین عنصر بزرگترین است (هر فضای ویژه به محور اول نزدیکتر از سایر محورها است) ، بنابراین قضیه فقط قول می دهد که دیسک برای ردیف 1 (که شعاع می تواند دو برابر مجموع از دو شعاع دیگر) را پوشش می دهد هر سه مقادیر ویژه.

تقویت قضیه [ ویرایش ]

اگر یکی از دیسک ها از سایرین جدا باشد ، دقیقاً یک مقادیر ویژه درج می کند. اگر با این وجود دیسک دیگری را ملاقات کند ، ممکن است که حاوی مقادیر ویژه ای نباشد (برای مثال ،A = {\ fill pmatrix} 0 & 1 \\ 4 & 0 \ end {pmatrix}} یا A = {\ fill pmatrix} 1 & -2 \\ 1 & -1 \ end {pmatrix}) در حالت کلی ، قضیه را می توان به شرح زیر تقویت کرد:

قضیه : اگر اتحادیه دیسک های k از اتحادیه دیسک های دیگر n  -  k جدا باشد ، اتحادیه قبلی حاوی دقیقاً k و دومی n  -  k مقادیر ویژه A است .

اثبات : بگذارید D ماتریس مورب با ورودی های برابر با مورب A باشد و اجازه دهید

{\ displaystyle B (t) = (1-t) D + tA.

ما از این واقعیت استفاده خواهیم کرد که مقادیر ویژه ای در کشور مداوم هستند تی، و نشان دهید که اگر مقدمات ویژه ای از یکی از اتحادیه ها به دیگری منتقل شود ، باید برای بعضی از آنها دیسک باشد. تی، که یک تضاد است.

بیانیه برای این درست است D = B (0). نوشته های مورب ازب (ت)هستند که از برابر ، در نتیجه مراکز محافل Gershgorin یکسان هستند، با این حال شعاع آنها می تی بار است که از A. بنابراین، اتحادیه مربوطه K دیسک ازب (ت)برای همه از اتحادیه nk باقی مانده جداستt \ in [0،1]. دیسک ها بسته هستند ، بنابراین فاصله دو اتحادیه برای A استd> 0. مسافت برایب (ت)یک تابع کاهش دهنده t است ، بنابراین همیشه حداقل d است . از مقدمات ویژهب (ت)یک تابع مداوم از t ، برای هر مقدمه مهم است\ lambda (t) از ب (ت)در اتحادیه k فاصله خود را نشان می دهدد (تی)از اتحادیه دیسک های دیگر nk نیز پیوسته است. به طور مشخصd (0) \ geq d، و فرض کنید \ lambda (1)در اتحادیه دیسک های nk نهفته است . سپسد (1) = 0بنابراین وجود دارد0 <t_ {0} <1 به طوری که 0 <d (t_ {0}) <d. اما این یعنی\ lambda (t_ {0})در خارج از دیسک های گرشورورین قرار دارد ، که غیرممکن است. از این رو\ lambda (1)در اتحادیه دیسک های k قرار دارد و قضیه اثبات شده است.

ملاحظات:

  • استمرار\ lambda (t)باید به معنای توپولوژی درک شود . کافی است نشان دهیم که ریشه ها (به عنوان نقطه ای از فضا)\ mathbb {C} ^ {n) عملکرد مداوم ضرایب آن است. توجه داشته باشید که نقشه معکوس که ریشه را به ضرایب نقشه می کند توسط فرمول های ویتا تشریح شده است (توجه داشته باشید برای چند جمله ای{\ displaystyle a_ {n} \ معادل 1) که می تواند یک نقشه باز ثابت شود . این ثابت می کند که ریشه در کل یک تابع مداوم از ضرایب آن است. از آنجا که ترکیب توابع مداوم دوباره مداوم است ،\ lambda (t) به عنوان ترکیبی از حل کننده ریشه و ب (ت) همچنین مداوم است.
  • مقدمه ویژه فردی\ lambda (t)می تواند با مقاصد خاص دیگر ادغام شود یا از تقسیم مقدمات قبلی ظاهر شود. این ممکن است مردم را گیج کرده و مفهوم مداوم را زیر سوال ببرد. با این حال ، هنگام مشاهده از فضای مجموعه مقادیر ویژه\ mathbb {C} ^ {n، مسیر هنوز یک منحنی مداوم است اگرچه لزوما در همه جا صاف نیست.

سخنان اضافه شده:

  • اثبات ذکر شده در بالا قابل بحث است (بطور صحیح) ...... دو نوع پیوستگی در مورد مقادیر ویژه وجود دارد: (1) هر مقادیر خاص یک تابع مداوم معمول است (چنین بازنمایی در یک فاصله واقعی وجود دارد اما ممکن است وجود نداشته باشد) بر روی یک دامنه پیچیده) ، (2) مقادیر ویژه به عنوان یک کل به معنای توپولوژیکی مداوم هستند (نقشه برداری از فضای ماتریس با متریک ناشی از یک هنجار به تاپل های بدون هماهنگ ، یعنی فضای کمتری از C ^ n تحت معادل جایگیری با القاء متریک) هر کدام از تداوم در اثبات قضیه دیسک Gerschgorin استفاده می شود ، باید توجیه شود که مجموع تعدد جبری مقادیر ویژه در هر منطقه متصل تغییر ناپذیر است. اثبات با استفاده از اصل بحث از تجزیه و تحلیل پیچیدهبه هیچ وجه مستلزم تداوم مقدماتی نیست. [1] . برای بحث و توضیح مختصر ، مراجعه کنید

[2]

برنامه [ ویرایش ]

قضیه دایره گرشگورین در حل معادلات ماتریس از فرم Ax = b برای x در جایی که b یک بردار است و A ماتریس با تعداد شرط زیاد مفید است .

در این نوع مشکل، خطا در نتیجه نهایی معمولا از همان است منظور از قدر به عنوان خطا در داده های اولیه ضرب در تعداد شرط . به عنوان مثال ، اگر b به شش مکان اعشاری شناخته شده است و شرط A برابر 1000 است ، می توانیم اطمینان داشته باشیم که x در سه نقطه اعشاری دقیق است. برای اعداد بسیار بالا شرایط ، حتی خطاهای بسیار ناچیز به دلیل گرد شدن می توانند تا حدی بزرگ شوند که نتیجه بی معنی باشد.

خوب است که تعداد شرط A را کاهش دهیم . این می تواند با پیش شرط انجام شود : یک ماتریس P به گونه ای که P ≈ A -1 ساخته می شود ، و سپس معادله PAx = Pb برای x حل می شود . با استفاده از دقیق معکوس از امر می تواند خوب اما پیدا کردن معکوس ماتریس چیزی است که ما می خواهیم برای جلوگیری دلیل هزینه محاسباتی است.

حال حاضر، از PA ≈ من که در آن من ، ماتریس واحد است، مقادیر ویژه از PA باید همه نزدیک به 1. با دایره قضیه Gershgorin، هر مقدار ویژه PA دروغ در یک منطقه شناخته شده است و بنابراین ما می توانیم یک برآورد تقریبی از چگونه خوب را تشکیل می انتخاب ما از P بود.

مثال [ ویرایش ]

برای تخمین مقدمات ویژه ای از قضیه دایره گرشگورین استفاده کنید:

این نمودار دیسک های به رنگ زرد حاصل از مقادیر ویژه را نشان می دهد. دو دیسک اول با هم همپوشانی دارند و اتحادیه آنها شامل دو مقدمه مهم است. دیسک های سوم و چهارم از سایرین جدا شده و هرکدام یک مقادیر ویژه ای دارند.

·A = {\ fill bmatrix} 10 & -1 & 0 & 1 \\ 0.2 & 8 & 0.2 & 0.2 \\ 1 & 1 & 2 & 1 & 2 & 1 \\ - 1 & -1 & -1 & -11 \\ end end {bmatrix}.

شروع با ردیف یکی، ما را به عنصر در قطر، دوم به عنوان مرکز برای دیسک. سپس عناصر باقیمانده را در ردیف می گیریم و فرمول را اعمال می کنیم:

\ sum _ {\ j \ neq i}} | a _ {{ij}} | = R_ {i

برای به دست آوردن چهار دیسک زیر:

D (10،2) ، \؛ D (8،0.6) ، \؛ D (2،3) ، \؛ text \ text و}} \؛ D (-11،3).

توجه داشته باشید که می توانیم با استفاده از فرمول در ستون های مربوط به ماتریس ، با استفاده از فرمول ، صحت دو دیسک آخر را بهبود بخشیم. د (2،1.2) وD (-11،2.2).

ارزشهای ویژه 9.8218 ، 8.1478 ، 1.8995 ، -10.86 است. توجه داشته باشید که این یک (ستون) ماتریس غالب مورب است :\ displaystyle | a_ {ii} |> \ sum _ {j \ neq i} | a_ {ji} |}. این بدان معناست که بیشتر ماتریسها در مورب قرار دارند و این مسئله توضیح می دهد که چرا مقادیر ویژه مقادیر بسیار نزدیک به مراکز حلقه ها هستند و تخمین ها بسیار مناسب هستند. برای یک ماتریس تصادفی ، ما انتظار داریم که مقادیر ویژه ای از مراکز حلقه ها بیشتر باشد.

منبع

https://en.wikipedia.org/wiki/Gershgorin_circle_theorem