基于最大熵原理下的最優(yōu)分割法

引 言

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

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

一、問題假設

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

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

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

二、預備知識

1.信息量

五、小 結

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