بخشی از مقاله
چکیده
با استفاده از محک محورگزین مارکویچ چ ونگ حل مساله فضای پوچ تنک را بررس م کنیم. بدین منظور، ابتدای ال وریتم کاهش رتبه را در نظر م گیرم و سپس روش برای تعیین پارامترهای این ال وریتم ارایه م کنیم تاال وریتم جدید برای مساله فضای پوچ تنک مناسب باشد. سپس این ال وریتم را پیاده سازی و عمل رد آنرا بر رویماتریس ضرایب مجموعه مسایل آزمون با یک پیاده سازی از ال وریتم کارا و شناخته شده برای مساله فضای پوچتنک از نقطه نظر زمان مورد نیاز دقت و میزان تنک پایه تولید شده مقایسه م کنیم. نتایج عددی نشان م دهند که الگوریتم پیشنهادی به طور مؤثر رقابت نزدی با الگوریتم کارای موجود دارد.
واژهdهای کلیدی: پایه پوچ تنک، مح محورگزین مارکویچ، روند کاهش پایه.
١ مقدمه
فرض کنید A = - a1, . . . , , am - T ∈ R m×n، .m ≤ n مساله فضای پوچ تنک عبارتست از یافتن ی پایه برای فضای پوچ A باکمترین تعداد درایه های ناصفر. این مساله در بسیاری از زمینه های مختلف ریاض ، مهندس و علوم کامپیوتر مانند برنامه ریزی غیر خط ، روشهاینقطه درون ظاهر م شود و در دست داشتن ی ال وریتم مؤثر برای حل آن بسیار با اهمیت است. بزای بررس بیشتر، ابتدا به تشریح رده ای از ال وریتمهای کاهش رتبه و مح محورگزین مارکویچ م پردازیم.
١.١ رده ال وریتمهای کاهش رتبه
اگرواری [4] در سال ٠۶١٩ روندی برای کاهش رتبه ی ماتریس ارایه و کاربرد آنرا برای حل دستگاه های خط بررس کرد. سپس، اباف ، برویدن و اسپدی اتو [1] این روند را به روش هایی موسوم به ABS توسیع دادند. برای سادگ در نمادگذاری، فرض کنید که ماتریس A رتبه ی سطری کامل دارد. ی روش ABS برای حل دستگاه خط Ax = b با ی بردار دلخواه آغازین x1 ∈ Rn و ی ماتریس دلخواه نا تکین H1 ∈ Rn×n شروع م کند. در تکرار iام، پس از محاسبه ی xi، جواب i − 1 معادله ی اول Ax = b، xi+1 که جواب i معادله ی اول و Hi+1 که سطرهای آن فضای پوچ i سطر اول A را تولید م کنند، محاسبه م شوند. بدین منظور در تکرار iام، zi طوری تعیین میشود که ziT Hiai ̸= 0 ، و بردار جستجو برابر qi = HiT zi قرار م ساخته م شود، که در آن، طول گام αi برابر است باگیرد. پس از آن جواب i − 1 معادله اول با xi+1 = xi + αiqiسپس، Hi+1 طوری بهنگام سازی م شود که Hi+1aj = 0، .1 ≤ j ≤ i برای این کار کاف است قرار دهیم:
که در آن، داریم .wiT Hiai ̸= 0 م توان نشان داد که در ی ال وریتم ABS داریم si = wiT Hiai ̸= 0 اگر و تنها اگر ai به طور خط مستقل از a1, a 2 . . . , ai−1 باشد. توسیع از روشهای ABS توسط چن [2] معرف شده است که تفاوت آن با در چ ونگ بهنگام سازی ماتریس Hi است. در این روند ماتریس Hi با رابطه ی Hi+1 = GiHi بهنگام سازی م شود که در آن، Gi ∈ Rji+1,ji طوری انتخاب م شود که در ادامه، در مورد انتخاب خاص از پارامتر ji که از آن استفاده خواهیم کرد، بیشتر بحث م کنیم. ابتدا توجه کنید که در تکرار اول داریم j1 = n و j2 م تواند n یا n − 1 باشد. در حالت کل ، اگر ji = n − t، آنگاه ji+1 م تواند n − t، n − - t + 1 - ، · · ·، n − i باشد . - 0 ≤ t ≤ i − 1 - توجه کنید که کوچ ترین مقدار مم ن برای ji+1 برابر n − i است. اگر در ی روند کاهش رتبه، Gi را طوری انتخاب کنیم که ji+1 = n −i، آنگاه سطرهای Hi+1 برای i سطر اول A تش یل ی پایه میدهند. گرچه روند های کاهش رتبه برای حل دستگاه های معادلات خط طراح شده اند، ول با انتخاب ji = n − i، م توان آن را به عنوان ال وریتم برای محاسبه ی فضای پوچ در نظر گرفت. با توجه به این که الگوریتم مورد بحث پارامترهای آزاد زیادی دارد، م توان امید داشت که با انتخاب مناسب این پارامترها پایه های پوچ مناسبی تولید کرد.
١.٢ محورگزین مارکویچ
فرض کنید rit و ctj، به ترتیب، تعداد درایه های ناصفر در سطر t و ستون jام ماتریس باق مانده پس از اعمال روش حذف گاوس روی ماتریس A ∈ R - m−i - × - n−i - باشد. فرض کنید که Ai زیر ماتریس باق مانده ی مربوط به تکرار iام در روش حذف گاوس و airs درایه ی سطر rام و ستون sام Ai باشد. محورگزین مارکویچ [5] یموضع آزمند است که در میان درایه های ماتریس باق ماندهدرایه ی ناصفر atrs را که متناظر با با عدد مارکویتز مینیمم یعن - rit − 1 - - ctj − 1 - ، در میان همه درایه هایی است که در نامساویصدق م کنند، انتخاب م کند، که در آن 0 < u ≤ 1، ی مقدار ثابت است. شرط - ۶ - به منظور ایجاد پایداری عددی، علاوه بر تنک در نظر گرفته شده است.
٢نتایج اصل
اکنون روند کاهش رتبه ی مؤثری را برای حل مساله ی پایه پوچ تنک ارایه م کنیم. م A ∈ Rm×n، که رتبه ی سطری کامل دارد، محاسبه کنیم. فرض کنید H1 ماتریس همان خواهیم ی پایه ی پوچ تنک برای ماتریس n × n است. در تکرار iام فرض کنید hkT،نتایج بدست آمده از الگوریتم پیشنهادی را با نتایج ی پیاده سازی از ال وریتم مؤثری که توسط کولمن و پوتن [3] ارایه شده است، مقایسه م کنیم. این دو الگوریتم از نظر زمان مورد نیاز و تنک پایه های تولید شده با هم مقایسه شده اند. از ماتریس ضرایب مسایل مجموعه نتلیب١ به عنوان مجموعه مسایل آزمون میکنیم. نتایج عددی مربوط به برخی از مسایل در جدول نشان میدهند که الگوریتم ارایه شده الگوریتم مؤثری است. در این جدول، dn، dn1 و dn2 به ترتیب چ ال مساله ی مورد آزمون، چ ال پایه ی تولید شده توسط ال وریتم کولمن و پوتن و الگوریتم پیشنهاد ما هستند. به همین ترتیب، t1، nnz1، t2 و nnz2 به ترتیب زمان مورد نیاز و تعداد درایه های ناصفر پایه ی تولید شده برای الگوریتم کولمن و پوتن و الگوریتم ارایه شده است.
