基于最大熵原理下的最優分割法

引 言

本文主要針對在不利用函數性質情況下，一元連續函數零點求解問題，對于這類問題我們常用的方法有二分法和黃金分割法.本文假設此類問題的解服從均勻分布，并把解的分布歸結為二項分布，還引進了信息論工具——最大熵原理，找出了最優的方法.最終比較了兩種算法各自的“優越性”，并把這種“優越性”具體量化.

最后，基于最大熵原理，本文還提出了另外一種更加切合實際的概率二分搜索法以及自適應概率二分法.

一、問題假設

假設1 在不利用函數性質情況下，對一元連續函數零點求解問題，一般情況下，我們采用的是分割法——即首先把含解區間分成若干份，然后逐個判斷，去掉不含解的區間，如此循環，直至含解區間的長度達到我們需要的精度.把一個區間多分一個點或者少一個點，并不會對結果幾乎沒有影響，為了簡化問題，在分割的時候，對于劃分的區間，為了保證各分區間有一致的形狀，我們不妨約定所有的分割區間都是左開右閉區間（以后我們討論的區間全部都是左開右閉區間），而且每次循環分割時都按照左開右閉的規則進行，以便保證以后所有劃分出來的區間都是左開右閉.

假設2 在搜索解區間的過程中，逐個判斷，去掉不含解的區間時，我們不妨約定按照從左至右的順序進行判斷.

假設3 根據坐標的可平移性，我們可以假設一元連續函數的零點在整個求解區間中服從均勻分布.

二、預備知識

1.信息量

五、小 結

本文根據坐標的可平移性，假設不知道函數性質情況下求解一元連續函數的零點服從均勻分布的基礎上，利用最大熵原理，從理論上比較出了最優的分割法搜索法.并在最大熵原理基礎上，提出了更加切合實際的概率二分搜索法以及自適應概率二分法.本文實際上已經提出了一種判斷各算法有效性的有效方法——最大熵原理.