دانلود کتاب Matrix Algorithms (به فارسی: الگوریتم های ماتریسی) نوشته شده توسط «G. W. Stewart»
اطلاعات کتاب الگوریتم های ماتریسی
موضوع اصلی: ریاضیات محاسباتی
نوع: کتاب الکترونیکی
ناشر: Society for Industrial and Applied Mathematics
نویسنده: G. W. Stewart
زبان: English
فرمت کتاب: djvu (قابل تبدیل به سایر فرمت ها)
سال انتشار: 1998
تعداد صفحه: 479
حجم کتاب: 3 مگابایت
کد کتاب: 9780898714142 , 0898714141 , 0898714184
نوبت چاپ: 1
توضیحات کتاب الگوریتم های ماتریسی
لطفاً هشدار دهید که این کتاب به‌شدت در جهت تئوری ماتریس طراحی شده است تا خود الگوریتم. بنابراین، اگر از ریاضیات بیزار هستید، بهتر است به دنبال کتاب های دیگری باشید که تئوری بسیار سبک تری مانند دستور العمل های عددی ارائه می دهند. با این حال، اگر با حروف یونانی یا فرمول های پیچیده منصرف نمی شوید و مشتاق یادگیری تئوری های پشت همه الگوریتم ها هستید، این کتاب برای شما مناسب است. اگرچه نویسنده ادعا می کند که مخاطب مورد نظر “غیر متخصص” است، اما به نظر من این کتاب بیشتر برای دانشمندان یا دانش آموزان مقاطع تحصیلی مناسب است تا برنامه نویسان معمولی.
نویسنده صراحتاً فرض می کند که شما مقداری برنامه نویسی و مقداری جبر خطی می دانید. اگرچه فصل 1 نظریه های اساسی ماتریس را توضیح می دهد، شما باید دانش پایه ماتریس قوی داشته باشید – مانند جمع ماتریس ها، تفریق ها، جابجایی ها، تعیین کننده ها، معکوس ها – همانطور که نویسنده در همان چند صفحه اول مواردی را بیان می کند. هنوز در فصل 1، نویسنده نظریه‌ها را زیاد می‌سازد، هم نظریه ماتریس و هم جبر خطی. او بسیاری از اصطلاحات مانند رتبه، هنجارها، تجزیه، تکینگی، و غیره را توضیح می دهد. او همچنین برهانی بر برخی قضایا ارائه می دهد. این نظریه های پیشرفته در فصل های بعدی مربوطه توسعه خواهند یافت.
فصل 2 کلمات کلیدی و نمادهای مورد استفاده در الگوریتم، مانند “برای”، “اگر” و غیره را مورد بحث قرار می دهد. شبه کد شبیه پاسکال است. در اینجا، او همچنین نمونه‌هایی از الگوریتم‌های «آسان‌تر» را ارائه می‌کند، مانند جایگزینی رو به جلو و وارونگی ماتریس مثلثی. او همچنین نماد کلاسیک Big O را به اختصار توضیح می‌دهد و از الگوریتم‌های نمونه به عنوان نمونه‌هایی در مورد نحوه محاسبه نماد Big O استفاده می‌کند. سپس، نحوه ذخیره ماتریس ها در حافظه و نحوه بهینه سازی الگوریتم بر اساس نحوه ذخیره ماتریس در حافظه به دنبال آن است. سپس، او به طور کاملاً مفصل در مورد چگونگی محاسبه خطای گرد کردن در الگوریتم‌ها و ثبات عددی یک الگوریتم معین بحث می‌کند. این آخرین بخش از فصل 2 برای کسانی که خواهان دقت هستند بسیار مهم است. این مسائل عددی در فصول بعدی نیز به طور کامل مورد بحث قرار خواهند گرفت.
فصل 3 در مورد حذف گاوسی، تجزیه LU، تجزیه Cholesky و انواع مربوط به آنها بحث می کند. نویسنده تمام تئوری های پشت آنها را توضیح می دهد، همراه با اثبات، بحث در مورد دقت / خطای گرد کردن، و عملکرد نظری Big-O. الگوریتم‌ها در شبه کد پاسکال ارائه شده‌اند که نماد آن در فصل 2 توضیح داده شده است. نویسنده همچنین درباره اینکه چگونه برخی از انواع مختلف سودمندتر از سایرین هستند (از نظر سرعت، ثبات عددی، و غیره) و اغلب با اثبات (یا سمت چپ) کامل می‌شوند، ارائه شده‌اند. به عنوان یک “تمرین” برای خواننده). تئوری های فصل 1 نیز در صورت نیاز مورد بازبینی و گسترش قرار می گیرند.
فصل 4 تجزیه QR و انواع آن را مورد بحث قرار می دهد. کامل با نظریه پس زمینه، اثبات، بحث در مورد دقت، و غیره. درست مانند فصل 3. همچنین در مورد مسائل به روز رسانی و چگونگی تطبیق QR با راه حل های خطی بحث می کند.
فصل 5 تجزیه های کاهش رتبه را مورد بحث قرار می دهد. اصلاحات تجزیه های قبلی برای مطابقت با نیازهای کاهش رتبه، تجزیه QLP و انواع تجزیه UTV. تئوری‌ها، اثبات‌ها، و بحث درباره دقت‌ها، طبق معمول همه در این مورد هستند.
صحبت از تئوری، عالی است. این کامل است و شواهد وجود دارد حتی زمانی که فکر می کنم آنقدرها ضروری نیست. با مطالعه این کتاب، تمام تئوری های پشت همه تجزیه های مورد بحث را درک خواهید کرد. مسائل عددی بسیار دقیق مورد بحث قرار گرفته است که خود قیمت این کتاب را توجیه می کند.
با این حال، نگرانی اصلی من این است:
1. کمبود نمونه های واقعی
بسیاری از مثال های مورد بحث در کتاب بسیار انتزاعی هستند. گاهی اوقات هیچ نمونه ای وجود ندارد. به عنوان مثال: هیچ نمونه ای در انجام تجزیه Cholesky وجود ندارد. نویسنده تنها زمانی مثال می‌زند که چرخش لازم باشد (و در نتیجه منجر به تغییرات کوچکی در الگوریتم می‌شود). در مورد موردی که نیازی به چرخش ندارد چطور؟ حتی با موردی که نیاز به چرخش دارد، مثال ها به صورت مرحله به مرحله ارائه نمی شوند. فرض بر این است که خواننده می داند که چند مرحله از الگوریتم ها قبلاً از یک ماتریس به ماتریس دیگر انجام شده است. در مورد ماتریس هسنبرگ، اصلاً نمونه ای وجود ندارد. این کتاب مطمئناً برای «غیرمتخصصان» در نظر گرفته نشده است.
2. تئوری و شواهد بسیار زیاد
من تمایل دارم بگویم که نظریه بیش از حد لازم وجود دارد. من اصلا اهل ریاضی نیستم من امیدوار بودم که این کتاب همانطور که نویسنده ادعا می کند کاربردی تر باشد.
3. مخفف BLAS
شاید این یکی یک آزار کوچک باشد. نویسنده از مخفف BLAS بسیار استفاده می کند. مانند “xeuib” که مخفف “X برابر است U^(-1) ضربدر B”. من با BLAS آشنا نیستم و باید به شکل 2.2 مراجعه کنم تا یکی را بفهمم.
همانطور که گفته شد، این کتاب محکمی برای توضیح تئوری های تجزیه اساسی است. درمان در جنبه برنامه نویسی و عمل گرا نسبتاً کم است. قطعاً برای افراد ضعیف و ضعیف نیست.
The author explicitly assumes that you know some programming and some linear algebra. Although chapter 1 explains basic matrix theories, you’ll need to possess strong basic matrix knowledge — such as matrix additions, substractions, transpositions, determinants, inverses — as the author glosses over those on the very first few pages. Still on chapter 1, the author builds up the theories a lot, both matrix theory and linear algebra. He explains many terms such as rank, norms, decompositions, singularity, etc. He also give some proofs on some theorems. These advanced theories will be developed in corresponding later chapters.
Chapter 2 discusses keywords and notations used in the algorithm, such as “for”, “if”, etc. The pseudocode looks like Pascal. Here, he also give some samples of “easier” algorithms, such as forward substitution and inversion of triangular matrix. He also explains the classical Big O notation briefly and use the sample algorithms as examples on how to compute the Big O notation out. Then, followed by how matrices are stored in the memory and how to optimize the algorithm based on how we store the matrix in the memory. Then, he discuses, quite elaborately, on how to compute rounding error on algorithms and numerical stability of a given algorithm. This last section of chapter 2 is extremely important for those who demands accuracy. This numerical issues will be thoroughly discussed in the later chapters too.
Chapter 3 discusses Gaussian Elimination, LU Decomposition, Cholesky decompositions and their respective variants. The author explains all theory behind them, complete with proofs, discussion on accuracy / rounding error, and Big-O theoretical performance. The algorithms are presented in Pascal-like pseudocode, whose notation described in chapter 2. The author also discuss how certain variants are more beneficial than others (in terms of speed, numerical stability, etc), again, often complete with proofs (or left as an “exercise” for the reader). Theories from chapter 1 are also revisited and expanded as needed.
Chapter 4 discusses QR decomposition and its variants. Complete with background theory, proofs, discussion on accuracy, etc. Just like in chapter 3. It also discusses updating issues and how to adapt QR to linear solutions.
Chapter 5 discusses rank-reducing decompositions. Modifications of previous decompositions to suit this rank-reducing needs, QLP decompositions, and variants of UTV decompositions. Theories, proofs, and discussion of accuracies are all in, as usual.
Speaking of the theory, it’s great. It’s thorough and the proofs are there even when I think it’s not that necessary. By studying this book, one will understand all the theory behind all the decompositions discussed. Numerical issues are discussed very thoroughly, which in itself justifies the price of this book.
However, my main qualms are:
1. Dearth of real examples
Many examples discussed in the book are way too abstract. Sometimes there are no examples at all. For example: There are no examples in doing Cholesky decomposition. The author only gives an example when the pivoting is necessary (and thus leads to small modification of the algorithm). What about the one that doesn’t require any pivoting? Even with the one that requires pivoting, the examples are not given as step-by-step run through. The reader is assumed to know which several steps of the algorithms have already taken place from one matrix to another. In the case of Hessenberg matrix, there are no examples at all. This book is certainly not intended for “nonspecialists”.
2. Way too much theory and proofs
I’m inclined to say that there are way too much theory than it is necessary. I’m not math-averse at all. I was hoping that this book is more practical as the author claims.
3. BLAS acronym
Maybe this one is a small annoyance. The author uses BLAS acronym a lot. Such as “xeuib” that stands for “X Equals U^(-1) times B”. I’m not familiar with BLAS and I have to keep refering to Figure 2.2 to figure one out.
That being said, this is a solid book for explaining theories behind basic decomposition. Treatment on the programming and pragmatic side is rather lacking. Definitely not for the faint-hearted.
دانلود کتاب «الگوریتم های ماتریسی»
