數(shù)值分析上機題(1)

《數(shù)值分析上機題(1)》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)值分析上機題一、城市水管應埋于地下多深1、問題背景在冬季寒冷的大城市，必須保證埋于地下的水管不凍結。在寒冷季節(jié)，地面土壤的溫度很低，而越深入地下溫度越高。因此，水管應該埋得越深越好。但相應的施工難度及成本也越大。問：在保證水管不凍結，埋水管的深度如何確定。2、建模由于土壤的熱傳導作用，冬季寒流到來后，地下土壤的溫度會逐漸降低，因此，它既是深度x，也是時間t的函數(shù)。經(jīng)仔細分析，有如下方程：說明：T(x,t):土壤溫度函數(shù)，x為深度，t為時間。Ti：寒流到來前的正常土壤溫度Ts：寒流季節(jié)的地面溫度易

2、知，方程左端為0到1之間，t=0時值為1，x=0時值為0要確定最合適的深度，可假設寒冷最長時間為tm由于為結冰溫度，則T(x,t)=0對度的x為所求。于是有：1、求解條件一、Google的PageRank算法1、問題背景互聯(lián)網(wǎng)(internet)的使用已經(jīng)深入到人們的日常生活中，其巨大的信息量和強大的功能給生產(chǎn)、生活帶來了很大的便利。隨著網(wǎng)絡信息量越來越寵大，如何有效地搜索出用戶真正需要的信息變得十分重要。自1998年搜索引擎網(wǎng)站Google創(chuàng)立以來，網(wǎng)絡搜索引擎成為解決上述問題的主要手段。199

3、8年，美國斯坦福大學的博士生LarryPage和SergeyBrin創(chuàng)立了Google公司，他們的核心技術就是通過PageRank技術對海量的網(wǎng)頁進行重要性分析。該技術利用網(wǎng)頁相互鏈接的關系對網(wǎng)頁進行組織，確定出每個網(wǎng)頁的重要級別（PageRank）。當用戶進行搜索時，Google找出符合搜索要求的網(wǎng)頁，并按他們的PageRank大小依次列出。這樣，用戶一般在顯示結果的第一頁或者前幾頁就能找到真正有用的結果。PageRank技術的基本原理是：如果網(wǎng)頁A鏈接到網(wǎng)頁B，則認為“網(wǎng)頁A投了網(wǎng)頁B一票”，

4、而且如果網(wǎng)頁A是級別高的網(wǎng)頁，則網(wǎng)頁B的級別也相應地高。2、數(shù)學建模假設n是Internet中所有可訪問網(wǎng)頁的數(shù)目，此數(shù)值非常大，在2010年已接近100億。定義n×n的網(wǎng)頁連接矩陣G=(gij)，若從網(wǎng)頁j有一個鏈接到網(wǎng)頁i，則gij=1,否則gij=0。矩陣G有如下特點：（1）G矩陣是大規(guī)模稀疏矩陣；（2）第j列非零元素，表示了從網(wǎng)頁j鏈接出去的所有網(wǎng)頁；（3）第i行非零元素，表示了鏈接到網(wǎng)頁i的所有網(wǎng)頁；（4）G中非零元素的數(shù)目為整個Internet中存在的超鏈接的數(shù)量；（5）記G矩陣行元素

5、之和,它表示第i個網(wǎng)頁的“入度”；（6）記G矩陣列元素之和,它表示第j個網(wǎng)頁的“出度”。要計算PageRank，可假設一個隨機上網(wǎng)“沖浪”的過程，即每次看完當前網(wǎng)頁后，有兩種選擇：（1）在當前網(wǎng)頁中隨機選一個超鏈接進入下一個網(wǎng)頁；（2）隨機地新開一個網(wǎng)頁。這在數(shù)學上稱為馬爾可夫過程，若這樣的隨機“沖浪”一直進行下去，某個網(wǎng)頁被訪問到的極限概率就是它的PageRank。設p為選擇當前網(wǎng)頁上鏈接的概率（比如，p=0.85），則1-p為不選當前網(wǎng)頁的鏈接而隨機打開一個網(wǎng)頁的概率。若當前網(wǎng)頁是網(wǎng)頁j，則如

6、何計算下一步瀏覽到達網(wǎng)頁i的概率（網(wǎng)頁j到i的轉移概率）？它有兩種可能性：（1）若網(wǎng)頁i在網(wǎng)頁j的鏈接上，其概率為p×1/cj+(1-p)×1/n；（2）若網(wǎng)頁i不在網(wǎng)頁j的鏈接上，其概率為(1-p)×1/n由于網(wǎng)頁i是否在網(wǎng)頁j的鏈接上由gij決定，網(wǎng)頁j到i的轉移概率為：應注意到的是,若cj=0意味著gij=0，上式改為aij=1/n。任意兩個網(wǎng)頁之間的轉移概率形成了一個轉移矩陣A=（aij），設矩陣D為各個網(wǎng)頁出度的倒數(shù)（若沒有出度，設為1）構成的n階對角陣，e為全是1的n維向量，則:設表示

7、某時刻k瀏覽網(wǎng)頁i的概率，向量x(k)表示當前時刻瀏覽各網(wǎng)頁的概率分布。那么下一時刻瀏覽到網(wǎng)頁i的概率為，此時瀏覽各網(wǎng)頁的概率分布為x(k+1)=Ax(k)當這個過程無限進行下去，達到極限情況，即網(wǎng)頁訪問概率x(k)收斂到一個極限值，這個極限向量x為各網(wǎng)頁的PageRank，它滿足Ax=x,且1、計算PageRank設定n×n的網(wǎng)頁連接矩陣G，以及選擇當前網(wǎng)頁鏈接的概率p，要計算特征值1對應的特征向量x易知

8、

9、A

10、

11、1=1，所以ρ(A)≤1.又考慮L=I-A，容易驗證它各列元素和均為0，則為奇異矩

12、陣，所以

13、I-A

14、=0，1是A的特征值。更進一步，用圓盤定理考察矩陣AT的特征值分布。顯然第j個圓盤Dj，其圓心ajj>0，半徑rj滿足ajj+rj=1，因此，除了1這個點外，圓盤上任何一點到圓心的距離（即復數(shù)的模）都小于1，這就說明，1是矩陣AT和A的唯一主特征值。對于實際的大規(guī)模稀疏矩陣A，冪法是求其主特征向量的可靠的、唯一的選擇。網(wǎng)頁的PageRank完全由所有網(wǎng)頁的超鏈接結構所決定，隔一段時間重新計算一次PageRank以反映互聯(lián)網(wǎng)的發(fā)展變化。此時將上一次計算的結果作為冪法